"Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente." (Wikipedia) Si no sabeis que es la recursividad, lo explico rápidamente: Es una función que se llama a si misma para obtener el resultado. Un consejo: Máximo cuidado a la hora de definir la condición de parada. Otro consejo: aunque nos digan en clase que los algoritmos recursivos son una solución elegante a ciertos problemas... ¡hay que evitar usarlos siempre que se pueda!


Vamos a ver un ejemplo. Regresemos a nuestro algoritmo para resolver Fibonacci:

public static long fib(int n) {
   if (n < 2) return n;
   long fib0 = 0;
   long fib1 = 1;

   for (int i=2; i <= n; i++) {
      fib1 = fib0 + fib1;
      fib0 = fib1 - fib0;
   }

   return fib1;
}

Y aquí la resolución con una función recursiva:

public static long fib(int n) {
   if (n < 2) return n;
   return fib(n-2)+fib(n-1);
}

¡Mucho más elegante! Si no se cumple la condición de parada, cuando n es menor que 2, la función se llama a si misma para calcular el valor de los dos elementos anteriores de la serie...

"La iteración es humana; la recursión, divina."

L. Peter Deutsch

Pues bien... por muy orgullosos que estemos de nuestro código, hay que usar la primera versión... ¿por qué? Es fácil: ¡Velocidad! En este ejemplo precisamente es fácil apreciar la diferencia. Para ello nos montamos un script sencillo usando el comando time:

#!/bin/sh

echo "RESULTADO ITERACIÓN FOR: " time java Fibonacci $1
echo "==========================="
echo "RESULTADO RECURSIVIDAD: " time java FibonacciRecursivo $1

Vamos a ver los resultados:

./compareFibonacci.sh 3
RESULTADO ITERACIÓN FOR: 3: 2  real 0m0.293s user 0m0.264s sys 0m0.028s 
=========================== 
RESULTADO RECURSIVIDAD: 3: 2  real 0m0.292s user 0m0.264s sys 0m0.028s
./compareFibonacci.sh 19
RESULTADO ITERACIÓN FOR: 19: 4181   real 0m0.291s user 0m0.252s sys 0m0.036s
===========================
RESULTADO RECURSIVIDAD: 19: 4181   real 0m0.308s user 0m0.268s sys 0m0.036s
./compareFibonacci.sh 35
RESULTADO ITERACIÓN FOR: 35: 9227465   real 0m0.291s user 0m0.232s sys 0m0.056s
===========================
RESULTADO RECURSIVIDAD: 35: 9227465   real 0m0.526s user 0m0.516s sys 0m0.032s
./compareFibonacci.sh 42
RESULTADO ITERACIÓN FOR: 42: 267914296   real 0m0.292s user 0m0.252s sys 0m0.036s
===========================
RESULTADO RECURSIVIDAD: 42: 267914296   real 0m6.374s user 0m6.352s sys 0m0.044s

¿Qué ocurre aquí? El mismo resultado, pero el algoritmo iterativo lo resuelve casi en el mismo tiempo para Fibonacci de 3, que para una entrada de 42... pero en cambio el algoritmo recursivo aumenta a casi 6 segundos y medio para la entrada de 42.

Conclusión: ¡Mejor resolver un problema con una función iterativa!