Recursividad terminal
Este post, es mas bien un post técnico, donde se explica un pequeño truco para aprender bien a realizar funciones que usen este tipo de recursividad terminal. Esto está especialmente pensado para aquellos que mañana se presentan al examen de PD en FIC.
Bien primero de todo repasemos unos pequeños conceptos básicos. La recursvidad se sabe que es una manera poco eficiente de implementar un algorirmo iterativo, pero también hay que decir que queda realmente comprensible el código. El caso es que la recursividad terminal es una forma mucho mas eficiente, simplemente haciendo que antes de cada llamada recursiva queden todos los cálculos realizados, consiguiendo así un menor consumo de memoria y un cálculo mucho mas rápido.
Bien pensemos en la función que calcula el factorial de un número.
let rec factorial = function
0 -> 1
| n -> n * (factorial – 1);;
Ahora que tenemos esto… pensemos como se implementaría esto con un bucle while en C por ejemplo…
int factorial (int n) {
int resultado = n
while (n > 0) {
resultado = resultado*n;
n–;
}
return resultado;
}
Ahora si nos fijamos en esa función… podemos darnos cuenta de que n es la variable que controla el número de veces que se tiene que realizar la operación, y resultado es el lugar donde vamos guardando el resultado calculado… Entonces… teniendo en cuenta que la recursividad terminal exige una variable donde guardar que es lo que nos queda por hacer y otra para guardar el resultado… Esto en ocaml quedaría de la siguiente manera…
let factorial = function
0 -> 1
| n -> let rec aux resultado n =
if (n > 0) then aux (resultado*n) (n-1)
else resultado
in aux n (n-1);;
Espero que os sirva de ayuda. Por si esto no os llega, para los que sepais inglés… aquí fué donde yo llegué a esta conclusión…
http://en.wikipedia.org/wiki/Tail_recursion
