Recursión en

Acerca de Recursión

Las funciones recursivas son funciones que se llaman a sí mismas.

Una función recursiva debe tener al menos un caso base y al menos un caso recursivo.

Un caso base devuelve un valor sin volver a llamar a la función. Un caso recursivo vuelve a llamar a la función, modificando la entrada para que en algún momento coincida con el caso base.

Este es un ejemplo que cuenta los elementos de un array.

def count:
  if length == 0 then
    0                       # base case
  else
    1 + (.[1:] | count)     # recursive case
  end;

([] | count),           # => 0
([11, 22, 33] | count)  # => 3

Una función recursiva puede tener muchos casos base y/o muchos casos recursivos. Por ejemplo, la sucesión de Fibonacci es una sucesión recursiva con dos casos base.

def fibonacci:
  if . == 0 then
    0
  elif . == 1 then
    1
  else
    (. - 1 | fibonacci) + (. - 2 | fibonacci)
  end;

10 | fibonacci          # => 55

Contar el número de apariciones de un valor dado x en un array tiene dos casos recursivos.

def count_occurrences(x):
  if length == 0 then
    0
  elif first == x then
    1 + (.[1:] | count_occurrences(x))
  else
    (.[1:] | count_occurrences(x))
  end;

[11, 22, 33, 22, 44] | count_occurrences(22)    # => 2

En la práctica, recorrer arrays y otras estructuras de datos enumerables se suele hacer con funciones integradas, como map y reduce, o usando flujos como [.[] | select(...)]. Por dentro, algunas funciones integradas están implementadas usando recursión.

Recursión infinita

Las funciones recursivas, si se implementan incorrectamente, puede que nunca devuelvan su resultado. Esto puede ser problemático porque cada vez que se llama a una función se almacena una referencia en memoria del lugar al que la máquina virtual debe devolver el resultado (en la pila de llamadas). Si una función recursiva se llama a sí misma infinitamente, es posible que se agote la memoria y que la máquina virtual se bloquee con un error de desbordamiento de pila.

Este problema de recursión infinita puede deberse a:

• Olvidar implementar un caso base.
• No definir el caso base como la primera cláusula.
• No modificar el argumento correctamente al hacer la llamada recursiva y, por tanto, no alcanzar nunca el caso base.

Optimización de llamadas de cola

Como se describe en Wikipedia:

Una llamada de cola es una llamada a una subrutina realizada como acción final de un procedimiento. Si el destino de una llamada de cola es la misma subrutina, se dice que la subrutina es recursiva de cola.

Fíjate en la implementación de fibonacci de arriba. El caso recursivo se llama a sí mismo dos veces. La última acción que la función debe realizar es una suma. Como la última acción no es una llamada a sí misma, esa función es recursiva, pero no recursiva de cola.

Algunos lenguajes implementan la optimización de llamadas de cola, de modo que la llamada de cola puede reutilizar el marco de pila actual en lugar de tener que añadir un marco nuevo a la pila de llamadas. Esto puede aportar beneficios de rendimiento, además de proteger contra el temido desbordamiento de pila.

jq sí que implementa la optimización de llamadas de cola, pero solo para funciones de aridad 0. La forma de aprovechar esto es definir una función «interna» de aridad 0 que reciba algún tipo de estado como entrada. La función interna puede modificar el estado según sea necesario y pasar el nuevo estado a la llamada recursiva de cola. La función externa crea el estado inicial y lo pasa a la función interna para iniciar la recursión.

Se podría implementar una función fibonacci recursiva de cola manteniendo la sucesión calculada hasta el momento como parte del estado.

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55