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.

Muy a menudo, cada caso se escribe en su propia cláusula de función.

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

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(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

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

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

Bucles mediante recursión

Debido a la inmutabilidad, los bucles en Elixir se escriben de forma diferente a los de los lenguajes imperativos. Por ejemplo, los bucles suelen tener este aspecto:

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

En un lenguaje funcional, no es posible mutar i (llamando a i++). Por lo tanto, los bucles tienen que implementarse con recursión.

El equivalente de un bucle for en Elixir tendría este aspecto:

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

En la práctica, iterar sobre arrays y otras estructuras de datos enumerables se hace casi siempre con el módulo Enum. En segundo plano, las funciones del módulo Enum están implementadas con recursión.

Ejecución infinita

Las funciones recursivas, si se implementan incorrectamente, podrían no devolver nunca su resultado. Esto puede ser problemático porque cada vez que se llama a una función se almacena una referencia en memoria, en el lugar donde 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 quedarse sin memoria, lo que provoca que la máquina virtual se bloquee (un error de desbordamiento de pila). La máquina virtual de Erlang, sobre la que se ejecuta Elixir, está especialmente optimizada para la recursión y la fiabilidad, por lo que puede pasar mucho tiempo antes de que los errores de recursión infinita sean evidentes o se produzcan bloqueos.

Este problema de ejecució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, no alcanzar nunca el caso base.