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 el argumento 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 o muchos casos recursivos (o ambos). 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 cuántas veces aparece 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, casi siempre se itera sobre arrays y otras estructuras de datos enumerables usando funciones integradas, como map y reduce, o usando streams como [.[] | select(...)]. Por dentro, algunas de esas funciones integradas están implementadas con recursión.

Recursión infinita

Las funciones recursivas, si se implementan mal, puede que nunca devuelvan su resultado. Esto puede ser problemático, porque cada vez que se llama a una función se guarda en memoria una referencia 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 falle 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 lo tanto nunca alcanzar el caso base.

Optimización de llamadas de cola

Como se describe en Wikipedia:

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

Fíjate en la implementación de fibonacci que vimos antes. El caso recursivo se llama a sí mismo dos veces. La última acción que debe realizar la función es una suma. Como esa última acción no es una llamada a sí misma, la función es recursiva, pero no es 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 agregar un marco nuevo a la pila de llamadas. Además de protegerte del temido desbordamiento de pila, esto puede traer beneficios de rendimiento.

jq sí 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 argumento. 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 se lo pasa a la función interna para iniciar la recursión.

Una función fibonacci recursiva de cola se podría implementar manteniendo la serie 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