Recursividad terminal en ocaml

Hace unos pocos días que en clase de Programación declarativa empezamos a usar la recursividad terminal. Es la forma de definir operaciones recursivas que no desborden la pila de activación de la memoria (lo que en inglés se conoce como “Stack Overflow”).
Lo bueno de las operaciones recursivas es que son relativamente fáciles de programar para hacer cosas de forma repetitiva. Sin embargo se corre el riesgo de desbordar la memoria o de no haber comprobado bien el algoritmo y entrar en una cadena de llamadas recursivas que jamás alcance un fin (algo parecido a un bucle infinito). Aunque esto último depende del programador (o de quién diseñe el algoritmo), con lo primero puede ayudarnos la recursividad terminal. Se trata de no dejar cuentas pendientes para no acumular operaciones sin resolver en la pila.

Lo bueno de la recursividad terminal es precisamente eso: permite que las operaciones recursivas sean más seguras y rápidas y que puedan llegar más lejos en los cálculos porque (virtualmente) siempre dispondrán de memoria para hacerlos. Lo malo es que no hay una mecánica establecida para transformar algo recursivo en algo recursivo terminal, y ni siquiera todas las operaciones definidas de forma recursiva pueden ser programadas de forma recursiva terminal.

Para comprender esto voy a explicar dos ejemplos que creo que son muy esclarecedores. Por un lado tenemos la función factorial y por el otro la sucesión de Fibonacci, clásicos ejemplos de definiciones recursivas. Las veremos de forma matemática, recursiva y recursiva terminal. ¿Porque estos dos ejemplos si son los que ya se dan el primer día de clase? ¿Porqué no buscar otros que puedan ayudar más y mejor a ser capaces de formular de forma terminal otras operaciones?
Bien, la respuesta a la primera pregunta es muy sencilla: Más o menos cualquiera con un nivel matemático básico puede entender el funcionamiento de ambas definiciones, por no decir que serán viejos amigos para muchos de los que estén cursando PD.
Por otro lado, aún siendo los ejemplos más comunes de recursividad, creo que marcan claramente dos formas de programar algo recursivo terminal. El factorial de un número solo necesita hacer una sola llamada recursiva en su definición mientras que un número de la secuencia de fibonacci necesita dos, lo que eleva muchísimo la complejidad del problema. Vamos allá.

Caso 1: El factorial
La operación factorial es la que multiplica un número entero positivo por todos sus anteriores hasta el 1:
n! = n * (n-1) * (n-2) ... * 1
por ejemplo:
5! = 5 * 4 * 3 * 2 * 1 = 120
Es evidente entonces que:
5! = 5 * 4!
El factorial de 1 es 1 y el de 0 es 0:
1! = 1
0! = 0

El factorial de 0 y 1 es 1:
0! = 1! = 1

Lo cual nos conduce a poder escribir esto en ocaml de forma muy simple:
let rec factorial n = if n < 2
     then 1
     else n * factorial (n-1);;

Este es el factorial escrito en forma recursiva, aunque claro, el factorial de n no se podrá calcular mientras no se haya resuelto el de n-1, éste a su vez tendrá que esperar por el de n-2 y así sucesivamente.

La estrategia que veo posible aplicar en este caso es pensar de nuevo el problema empezando en 1 y acabando en n. Es decir, tomando el ejemplo anterior, hacer n multiplicaciones:
5! = 1 * 2 * 3 * 4 * 5
De modo que podemos sencillamente realizar una multiplicación anotando su resultado hasta que hayamos hecho n multiplicaciones:
let factorial n = if n < 2
     then 1
     else let rec factorial (i, r) = if i = n
          then i*r
          else factorial (i+1, i*r)
     in factorial (2,1);;

¿Como funciona esto?
Bien, en primer lugar debemos fijarnos en que la función principal ya no es recursiva. En cambio, distinguimos los casos base en ella (aquellos en los que n es menor que 2) porque su solución es directa.
La recursiva (planteada en el else) es ahora una función interna (también llamada factorial, para protegerla aprovechándonos del principio de ocultación de la información) con dos argumentos, que inicialmente se establecen a 2 y 1 (prestemos atención a la ultima línea, let... in factorial (2,1);; ).
El primer argumento, i, establece cuántas multiplicaciones estamos haciendo (recordemos que necesitamos hacer hasta n), y el segundo argumento, r, sencillamente va guardando el resultado calculado hasta el momento. Por ese motivo evitamos depender de que se resuelvan cuentas antes de calcular algo: el resultado del que íbamos a depender ya lo llevamos nosotros a buen recaudo.
El primer argumento nos interesa que sea el número 2, porque los casos de 1! y 0! se resuelven de forma directa antes en el condicional if. Obviamente, r será el resultado del factorial del numero anterior. Como empezamos en 2, el factorial de su anterior es 1! = 1.
Cada vez que se ejecute la función, se comprobará si estamos ya en la iteración que queremos. Si es así, bastará con devolver la multiplicación de ese número por r (que es el resultado del factorial del anterior, que traiamos ya guardado de antemano). Si no estamos en la iteración que necesitamos, aumentamos i en 1, calculamos el factorial de la ultima iteración y de nuevo se ejecutará la función.

Una version alternativa puede ser:
let factorial n = if n < 2
     then 1
     else let rec factorial (i, r) = if i = n
         then r
         else factorial (i+1, (i+1)*r)
     in factorial (2, 2);;

En esta versión, el factorial ya va calculado en cada iteración porque es calculado en la propia llamada recursiva del else. En cualquier caso es la misma idea.
Lo ideal para comprender su funcionamiento es hacer con papel y lápiz las instrucciones que se van ejecutando para el factorial de algún número como el 6 o el 7. Desgraciadamente el rango de números enteros del ordenador es insuficiente para mostrar el factorial de un numero tan bajo como el 13 y evitar esto no es el motivo de este post, pero trataré de cubrir este escollo en otra entrada haciendo uso de la librería “Num”.

Caso 2: La sucesión de Fibonacci
La sucesion de Fibonacci es aquella que asocia el 0 al 0, el 1 al 1, y a cada numero entero siguiente, la suma de los dos anteriores:
Fib(0) = 0
Fib(1) = 1
Fib(2) = 1 porque (1 + 0)
Fib(3) = 2 porque (1 + 1)
Fib(4) = 3 porque (2 + 1)
Fib(5) = 5 porque (3 + 2)
Fib(6) = 8 porque (5 + 3)
etc.
La solución más natural pudiera ser:
let rec fibonacci n = if n < 2
   then n
   else fibonacci (n-1) + fibonacci (n-2);;

Aunque pueda parecer algo muy sencillo, la complejidad es enorme. Tanta, que calcular el fibonacci de 30 puede llevarle varios segundos a una máquina actual; cuando hacerlo con papel y lapiz es cuestion de un minuto o menos. El problema radica en la doble llamada recursiva del else. Para calcular el fibonacci de 30, hay que tener calculado el fibonacci de 29 y el de 28. Para el de 29 necesitamos el de 28 y el de 27, mientras que para el de 28 necesitamos el de 27 y el de 26.
Y así sucesivamente, las operaciones se van ramificando y no resulta tan sencillo. Quizás en el momento de leer esto, las máquinas sean más potentes, pero para numeros menores de 50 la cosa se complica sorprendentemente. Calcular el fibonacci de 38 le ha llevado a mi cpu más de 16 segundos.
Como dato anecdótico calculado por el profesor: calcular el fibonacci de 100 podría llevarle varios millones de años. Literalmente.

Para resolver esto de forma recursiva terminal, aplicaré otra estrategia: dado que hay muchas operaciones repetitivas, procuraremos no tener que hacerlas. Al igual que en el factorial siempre llevábamos el resultado anotado, aquí llevaremos los resultados (dos, concretamente) que precisemos.
Consideremos i el numero cuyo fibonacci queremos calcular, a el fibonacci de su anterior y aa el fibonacci de su ante-anterior:
Fib(i) = a + aa
Si conseguimos llevar a y aa calculados en cada iteracion, solo habrá que devolver su suma. Una primera aproximación podría ser:
let fibonacci n = if n < 2
   then n
   else let rec fibonacci (i, a, aa) = if i = n
     then a + aa
     else fibonacci (i+1, a+aa, a)
   in fibonacci (2, 1, 0);;

¿Como funciona esto?
De nuevo, la función principal deja de ser recursiva y controla los casos base (0 y 1) con el condicional if. En el else, los resultados se calculan con una función recursiva interna. El secreto está en que no se calcula el fibonacci como tal, sino que se hacen las sumas de los numeros tal y como lo haría una persona con papel y lápiz. Comenzando en el 2, su fibonacci será la suma de 0 y 1. Por lo tanto (ver else) el fibonacci de 3 se calculará en una llamada recursiva cuyos parámetros son:
fibonacci (i+1, a+aa, a)
En la iteración del 2, tal y como se define en el let in:
fibonacci (2, 1, 0)
En la iteración del 3…
fibonacci (2+1, 1+0, 1)
o lo que es lo mismo:
fibonacci (3, 1, 1)
que al sumar a y aa…
a+aa = 1+1 = 2
y 2 es precisamente el fibonacci de 3. De nuevo, lápiz y papel serán grandes aliados. Es tal la mejora que se produce, que ahora podemos calcular números altísimos casi de forma instantánea . De hecho, nos saldremos del rango de numeros enteros antes de apreciar el tiempo que el ordenador emplea en terminar los cálculos, concretamente en el numero 45.

Una última reflexión…
En uno de los libros de Java que estuve empleando este año (‘Introducción a la programación con Java: Un enfoque orientado a objetos’, de David Arnow y Gerald Weiss) leí una de las mejores definiciones de recursividad que he visto:
Programar algo recursivo requiere pensarlo desde una postura vaga.
Por ejemplo, si tengo que fregar toda una pila de platos, puedo fregar uno y mandarle el resto a otra persona o decir que terminé si no quedan platos en la pila. El que venga detrás mía actuará igual que yo y al final, los platos quedarán lavados. Es la misma idea del factorial. Yo no se cuanto vale el factorial de 3, pero sé que es el resultado de multiplicar 3 por el factorial de 2, etc.
Sin embargo, tras haber escrito esto también llego a la conclusión de que para programar algo de forma recursiva terminal, primero hay que razonar el problema con lápiz y papel.
Si es más simple hacerlo con lápiz y papel (ya sean cuentas o diagramas de flujo de un programa), como en el caso de la recursividad de la sucesión de Fibonacci, lo más probable es que tenga que simular ese efecto en el ordenador: el efecto de poder guardar en una variable operaciones ya calculadas para no tener que repetirlas. Sean una o varias.
Ya más objetivamente hablando de Ocaml, por las particularidades de su sintaxis, vale la pena seguir esos dos pasos: desglosar una función recursiva en una función anidada en otra. En la primera podemos controlar directamente los casos base y dejar el carácter recursivo para una función interna, protegida de cara al usuario y en la que podemos permitirnos usar más parámetros según nuestras necesidades. Por otro lado, debemos recurrir a la librería “Num” para poder tratar con resultados numéricos enteros tan grandes.

Millones de años? En serio?
Las carcajadas en clase fueron sonoras. Algo tan simple como pudiese ser calcular el Fibonacci de 100 con papel y lapiz (cuestión de unos pocos minutos) se transformaría en millones de años si empleasemos un ordenador de potencia media y la definición recursiva de Fibonacci. ¿Convence esto al respetable de lo necesaria que es la recursividad terminal? ¿Y si en vez de calcular un número de la sucesión de Fibonacci hubiese que predecir terremotos o controlar el goteo de los pacientes de un hospital? Aún no puedes creerlo, ¿eh? 😀
Antes de que pongas tu ordenador a trabajar, usemos algo de aritmética para calcular el tiempo que necesitarías.
Supongamos que mi netbook Asus EeePC 901 (1.6Ghz, 1gb de ram a 533Mhz) puede calcular fib(35) en unos escasos 4 segundos. La complejidad de los cálculos de la sucesión de Fibonacci es de:
k = (1 + (sqrt 5)) / 2
Podemos trasladar esto a ocaml:
let k = (1. +. sqrt 5.) /. 2.;;
lo que (al resolver) produce un número irracional tradicionalmente conocido como el número áureo: 1.61803398874…
Si quisieramos calcular el Fibonacci de 45, estaríamos calculando 10 números más allá del fib(35) del que hablamos hace un par de líneas. Éste tardaba 4 segundos, así que el tiempo empleado en calcular fib(45) será sencillamente el resultado de la siguiente operación (aproximadamente):
(complejidad ^ diferencia) * tiempo
Recordemos que la exponenciación de numeros reales en ocaml se escribe “**“, por lo tanto:
k ** 10. *. 4.;;
Que da un resultado de 491.967477…
Esto quiere decir que se tardan más o menos 490 segundos en calcular fib(45) con la definición recursiva tradicional de la sucesión de Fibonacci. Unos 8 minutos que se pueden comprobar sin dificultad:
let t1 = Sys.time();;
fib (45);;
let t2 = Sys.time();;
let t = t2 -. t1;;

Como dato: con 2 gb de ram y el procesador en modo rendimiento, tan solo se ha reducido el tiempo empleado a 7 minutos aproximadamente. ¿Que pasa entonces con el Fibonacci de 100? ¿Como se llega a una diferencia tan brutal?
Pues bien, siguiendo con lo hecho en el ejemplo anterior: entre 35 y 100 hay 65 números. Es decir, hay 65 veces la complejidad de fib(35), que tardaba 4 segundos. Por lo tanto:
k ** 65. *. 4.;;
El resultado es: 153552399572044.344 segundos.
Dividimos este número entre 60, obtenemos minutos; de nuevo entre 60 y obtenemos horas. Entre 24 nos dará días y entre 365.25 obtendremos años:
let total = 153552399572044.344 /. 3600. /. 24. /. 365.25;;
El resultado es: 4865781.92169380281 años aproximadamente. En letra:
Un poco más de cuatro millones ochocientos sesenta y cinco mil setecientos ochenta y un años
¿Convencido ahora? 🙂

Entrada en wikipedia sobre la sucesión de Fibonacci
Entrada en wikipedia sobre el número áureo

Anuncios

3 comentarios sobre “Recursividad terminal en ocaml

  1. Que sepas que el factorial de 0 es 1 y no 0, por lo demás hasta te explicas bien.
    If n=o then 1
    es irrelevante para los demás resultados, pero para el mismo resultado de 0 o seria efectivo.
    Besosososos gordooooooo

    Me gusta

    1. Hola Pris,
      efectivamente 0!=1, gracias por tu comentario y por la corrección.
      También he corregido algunos detalles extra con lo que ahora debería estar todo bien (o eso espero…) 😀
      Un saludo!

      Me gusta

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s