Recursión en

Acerca de Recursión

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

Una función recursiva necesita 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.

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 distinta a los lenguajes imperativos. Por ejemplo, los bucles suelen verse así:

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

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

El equivalente a un bucle for en Elixir se vería así:

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. Internamente, las funciones del módulo Enum están implementadas usando recursión.

Ejecución infinita

Las funciones recursivas, si se implementan de forma incorrecta, podrían no devolver nunca su resultado. Esto puede ser un problema porque cada vez que se llama a una función, se almacena una referencia en memoria donde la VM debería devolver el resultado (en la pila de llamadas). Si una función recursiva se llama a sí misma infinitamente, es posible quedarse sin memoria y provocar que la VM colapse (un error de desbordamiento de pila). La VM de Erlang, sobre la que se ejecuta Elixir, está especialmente optimizada para la recursión y la fiabilidad, así que puede pasar mucho tiempo antes de que los errores de recursión infinita sean evidentes o de que ocurran fallos.

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 llegar nunca al caso base.