Los lenguajes funcionales tienen la capacidad de ser útiles utilizando la recursividad de forma sencilla y eficiente. Es la base de mucho de estos lenguajes. Si quieres saber más de estos detalles y optimizaciones los analizamos en este artículo.
Para poder entender todos los problemas y beneficios que tienen nuestras herramientas, hay que tener en cuenta cómo funciona la recursividad.
En todo algoritmo recursivo siempre que se realiza una llamada, el sistema la tiene que guardar de alguna forma, tiene que conocer el estado de cada una de las llamadas anteriores. Lo común en la mayoría de lenguajes es añadirlo en la pila con el estado actual. Hay que recordar que la pila es dinámica, y por eso se tiende a guardar ahí, ya que no sabemos cuantas llamadas se harán.
Alternativa a la recursividad
La resursividad tiene una alternativa en la mayoría de casos. Los algoritmos se pueden plantear de diferente forma para poder obtener una misma solución. Un ejemplo es el algoritmo de fibonacci. Este algoritmo se puede plantear de forma recursiva o de forma iterativa.
Ejemplo recursivo
# Ejemplo de https://www.geeksforgeeks.org
def Fibonacci(n):
# First Fibonacci number is 0
if n==1:
return 0
# Second Fibonacci number is 1
elif n==2:
return 1
else:
return Fibonacci(n-1)+Fibonacci(n-2)
Ejemplo iterativo
# Ejemplo de https://www.geeksforgeeks.org
def fibonacci(n):
a = 0
b = 1
if n == 0:
return a
elif n == 1:
return b
else:
for i in range(1,n):
c = a + b
a = b
b = c
return b
Así mismo se podrían hacer otro tipos de solución en función del lenguaje de programación. Por ejemplo, devolver una función que genera estos números bajo demanda.
Optimizaciones usando recursividad
En los casos de utilizar recursividad por la cola, lo que realmente se quiere es el valor de la última llamada recursiva. Por lo tanto, el compilador/interprete/maquina virtual puede limpiar todas las llamadas y utilizar el valor de la última llamada ahorrándonos volver atrás.
Imagen obtenida de Tail Recursion Is Its Own Reward: Wait, What is Tail Recursion?
La recursividad suele ser lenta, aunque los lenguajes funcionales se basan en el concepto de la recursividad. Estos tienen optimizadores al ejecutar que buscan patrones que se puedan mejorar. Pero depende del tipo de función que plantees. Hace un tiempo se planteó este mismo problema en stackoverflow, en una de las respuestas se puede ver claramente la optimización. Dos implementaciones diferentes. Una de ellas con recursividad por la cola, y la otra con recursividad normal. El primer caso se optimiza y tarda menos en ejecutar. Menor número de llamadas y cambios de contexto, se puede ver en la imagen superior.
Conclusión
Por lo tanto, la recursividad puede ser algo muy potente. Pero todo gran poder conlleva una gran responsabilidad. Los lenguajes funcionales se basan en la recursividad y la gran potencia de ésta. En los demás lenguajes se puede realizar y depende del programador el uso que se le dé.
Los lenguajes funcionales lo utilizan cómo definición, ya que se suele permite definir una misma función por partes, basándonos en sus parámetros: valor de éstos, tipo de algunos de ellos o el número de parámetros. De esta forma definir una función como fibonacci en Haskell, quedaría de la siguiente forma:
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Existen mejores implementaciones, se pueden ver en la Wiki Haskell.
Supongamos que queremos definir la suma de todos los elementos de una lista. Lo primero es definir qué tipo de parámetros tenemos de entrada y salida. Lo siguiente definimos el caso base, si nos llega una lista vacia devolvemos la unidad. Por último definimos que dado una lista, obtenemos el primer elemento (x) y los restantes de la lista (xs en forma de lista). Sumamos el primer elemento con la suma del resto de los elementos, una llamada recursiva a la misma función con el resto de elementos (xs). Definición en Haskell:
sumarLista :: [Int] -> Int
sumarLista [] = 0
sumarLista (x:xs) = x + sumarLista xs
Si quieren saber más sobre la recursividad, pueden leer Recursividad: ¿Cuándo debo utilizarla?
Fuentes
Python Program for Fibonacci numbers - GeeksforGeeks
Tail Recursion Is Its Own Reward: Wait, What is Tail Recursion?