miércoles, 29 de abril de 2015

Recursividad Terminal (Tail Recursion)

Introducción


Seguro que sabes lo que es la Recursividad: la definición de una función (o procedimiento) requiere de invocarse a sí misma con otros argumentos hasta alcanzar un caso base (situación en la que no es necesario invocarse a sí misma para obtener el resultado). El ejemplo típico es la función matemática factorial:

factorial(N)     si N es 0 entonces 1//Caso base.
en otro caso, N * factorial(N-1) //Llamada recursiva.

En una función recursiva, para poder calcular el valor de la función hay que esperar hasta haber calculado el valor de todas las llamadas recursivas (puede haber varias, como en la Sucesión de Fibonacci por ejemplo).

La programación recursiva tiene ventajas y desventajas respecto a la programación iterativa: suele simplificar mucho el algoritmo pero suele ser más lenta y sobre todo, es muy propensa al desbordamiento de la pila de ejecución (stack overflow).

Recursividad Terminal


En la Recursividad Terminal (Tail Recursion en inglés), aunque una función se invoque a sí misma, no necesita esperar al resultado de la invocación recursiva, sino que antes de invocarse a sí misma, realiza todos los cálculos necesarios, de modo que en la última llamada (la correspondiente a un caso base) ya se te tenga el resultado final.

La idea es pasar el resultado parcial a la llamada recursiva en vez de esperar a que sea ésta la que lo devuelva. En otras palabras, realizar los cálculos a medida que se desciende recursivamente en vez de hacerlo a medida que se asciende al deshacer la pila de llamadas.

Si el compilador/intérprete es suficientemente inteligente, detectará que no es necesario almacenar el frame (ventana, marco o tradúcelo como quieras) de cada invocación en la pila de ejecución, y que, al llegar al final, no es necesario deshacer la pila de llamadas. Esta optimización se conoce como Tail Call Optimization (TCO).

De ese modo, se ahorra memoria (evitando los problemas de desbordamiento de la pila de ejecución) y se aumenta muchísimo el rendimiento (se evitan todas las operaciones de manejo de la pila de ejecución), aunque el rendimiento podrá ser mejor o peor dependiendo del algoritmo en sí.

Ejemplo


El concepto es bastante extraño y complicado de explicar; es mucho mejor ver un ejemplo. Los ejemplos se han ejecutado con el intérprete GNU CLISP v2.49+ ejecutable online en el siguiente enlace:


A continuación se puede ver un programa en Common Lisp para invertir el orden de los elementos de una lista (reverse). El código fuente completo está disponible en este enlace:


a) Recursión Normal


Esta versión está escrita con recursión normal: en cada invocación, el resultado consiste en encolar el primer elemento al resultado de la invocación recursiva con el resto de elementos. El caso base es cuando se recibe una lista vacía, devolviendo una lista vacía también.

;Normal recursion
(defun my_reverse (a_list)
    (cond
        ((null a_list) nil)
        (t (append
                (my_reverse (rest a_list))
                (list (first a_list))
           ) 
        )
    )
)

(trace my_reverse)
(write (my_reverse '(1 2 3 4 5)))

A continuación se muestra la traza de ejecución:

;; Tracing function MY_REVERSE.                                                                                                                                                      
1. Trace: (MY_REVERSE '(1 2 3 4 5))                                                                                                                                                  
2. Trace: (MY_REVERSE '(2 3 4 5))                                                                                                                                                    
3. Trace: (MY_REVERSE '(3 4 5))                                                                                                                                                      
4. Trace: (MY_REVERSE '(4 5))                                                                                                                                                        
5. Trace: (MY_REVERSE '(5))                                                                                                                                                          
6. Trace: (MY_REVERSE 'NIL)                                                                                                                                                          
6. Trace: MY_REVERSE ==> NIL                                                                                                                                                         
5. Trace: MY_REVERSE ==> (5)                                                                                                                                                         
4. Trace: MY_REVERSE ==> (5 4)                                                                                                                                                       
3. Trace: MY_REVERSE ==> (5 4 3)                                                                                                                                                     
2. Trace: MY_REVERSE ==> (5 4 3 2)                                                                                                                                                   
1. Trace: MY_REVERSE ==> (5 4 3 2 1)                                                                                                                                                 
(5 4 3 2 1)  

Se puede comprobar que la lista en orden inverso se construye desde abajo hacia arriba.

b) Recursión Terminal


Ahora se muestra como quedaría el algoritmo utilizando recursividad terminal. La idea es apilar el primer elemento de in_list a out_list y pasar el resultado de eso como out_list a la invocación recursiva con el resto de in_list. Y en el caso base (in_list está vacía), ahora simplemente se devuelve el argumento out_list sin más.

Ha sido necesario cambiar la interfaz de la función para que reciba 2 argumentos en vez de uno, y algo muy importante, la primera invocación deber realizarse con el valor correcto para el argumento out_list: una lista vacía. Por eso se utiliza una función envoltorio (wrapper).

;Tail recursion
(defun my_reverse_tail_inner (in_list out_list)
    (cond
        ((null in_list) out_list)
        (t (my_reverse_tail_inner
                (rest in_list)
;Alternativa al append.
;                (cons (first in_list) out_list)
                (append
                    (list (first in_list))
                    out_list
                )
            )
        )
    )
)

(defun my_reverse_tail (a_list)
    (my_reverse_tail_inner a_list nil)
) 

(trace my_reverse_tail_inner)
(trace my_reverse_tail)
(write (my_reverse_tail '(1 2 3 4 5)))

A continuación se muestra la traza de ejecución:

;; Tracing function MY_REVERSE_TAIL_INNER.                                                                                                                                           
;; Tracing function MY_REVERSE_TAIL.                                                                                                                                                 
1. Trace: (MY_REVERSE_TAIL '(1 2 3 4 5))                                                                                                                                             
2. Trace: (MY_REVERSE_TAIL_INNER '(1 2 3 4 5) 'NIL)                                                                                                                                  
3. Trace: (MY_REVERSE_TAIL_INNER '(2 3 4 5) '(1))                                                                                                                                    
4. Trace: (MY_REVERSE_TAIL_INNER '(3 4 5) '(2 1))                                                                                                                                    
5. Trace: (MY_REVERSE_TAIL_INNER '(4 5) '(3 2 1))                                                                                                                                    
6. Trace: (MY_REVERSE_TAIL_INNER '(5) '(4 3 2 1))                                                                                                                                    
7. Trace: (MY_REVERSE_TAIL_INNER 'NIL '(5 4 3 2 1))                                                                                                                                  
7. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
6. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
5. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
4. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
3. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
2. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
1. Trace: MY_REVERSE_TAIL ==> (5 4 3 2 1)                                                                                                                                            
(5 4 3 2 1) 

Se puede ver que la lista en orden inverso se va construyendo desde arriba hacia abajo y que al llegar al caso base, ya está completamente construída, por lo que se deshace la pila devolviendo siempre lo mismo: el resultado final. En este caso, aparece una llamada más, la correspondiente a la función envoltorio (wrapper).

En este caso, también se podría simplificar el código utilizando la función cons para apilar un elemento al comienzo de una lista (en el caso de recursion normal hay que encolar usando la función append), simplificando mucho el código y reduciendo su coste.

Demostración de Tail Call Optimization


El intérprete indicado previamente permite aplicar Tail Call Optimization (TCO), pero para ello hay que precompilar la función utilizando compile.

Hasta donde mi conocimiento alcanza, es complicado desmostrar que se aplica TCO:
  • una vez compilada una función (optimizada o no), no se puede tracear (sólo aparecerá una invocación).
  • habría que acceder al código generado (¿es eso posible?) y además analizarlo para entenderlo...
Así que, he demostrado empíricamente que efectivamente se aplica TCO. La idea es averiguar cuán grande puede ser una lista sin que se desborde la pila al invertir el orden de sus elementos. Utilizando el intérprete indicado previamente, fui aumentando el tamaño de la lista (límite del loop) del siguiente programa:

(compile 'my_reverse)
(compile 'my_reverse_tail_inner)

;normal: se desborda la pila con menos de 35000 elementos.
(time (write (list-length (my_reverse (loop for n from 1 to 34000 by 1 collect n)))))
(write-line "")

;terminal con tantos elementos como la normal.
(time (write (list-length (my_reverse_tail (loop for n from 1 to 34000 by 1 collect n)))))
(write-line "")

;terminal: prueba de que se puede utilizar con una cantidad de elementos enorme.
(time (write (list-length (my_reverse_tail (loop for n from 1 to 3400012 by 1 collect n)))))
(write-line "")

La versión normal (my_reverse) se desborda con menos de 35000 elementos, mientras que con la versión terminal (my_reverse_tail) no conseguí desbordar la pila ni con varios millones de elementos.

Como datos orientativos, en una de las ejecuciones obtuve los siguientes resultados:

34000                                                                                                                                                                                
Real time: 38.68157 sec.                                                                                                                                                             
Run time: 38.663563 sec.                                                                                                                                                             
Space: 9248826160 Bytes                                                                                                                                                              
GC: 9157, GC time: 29.230534 sec.                                                                                                                                                    
34000                                                                                                                                                                                
Real time: 0.052549 sec.                                                                                                                                                             
Run time: 0.052638 sec.                                                                                                                                                              
Space: 1642160 Bytes                                                                                                                                                                 
GC: 1, GC time: 0.002901 sec.                                                                                                                                                        
3400012                                                                                                                                                                              
Real time: 6.269858 sec.                                                                                                                                                             
Run time: 6.099169 sec.                                                                                                                                                              
Space: 163210736 Bytes                                                                                                                                                               
GC: 21, GC time: 0.995367 sec.                                                                                                                                                       

Se puede observar una descomunal diferencia de velocidad, siendo la versión normal lentísima respecto a la terminal.

El consumo de memoria de la versión normal también es muy superior. Y se puede observar que el Garbage Collector apenas se dispara en la versión terminal.

Conclusión


Algo muy interesante de la Recursividad Terminal es que no es necesario almacenar las llamadas recursivas en la pila de ejecución, lo que evita su desbordamiento. Además, en teoría, podría permitir realizar una implementación recursiva en un lenguaje que no tenga soporte para ello.

Un punto negativo de la Recursividad Terminal está en que hay que cambiar la interfaz de la función para añadir el argumento "de salida o acumulador" y que además, hay que cerciorarse de invocarla con el valor inicial adecuado para dicho argumento; para esto último es recomendable crear una función envoltorio (wrapper) que se encargue de ello mostrando una interfaz equivalente a la versión no terminal.

Lo que a mí me parece más interesante, es que se trata una solución recursiva alternativa, que tal vez permita implementar algo recursivamente que de otro modo no se pueda. Por ejemplo, si en Common Lisp no se dispusiera de la función append (encolar), no se podría realizar la implementación normal, pero sí la terminal utilizando la función cons (apilar).

Enlaces


Enlaces de interés relacionados con este artículo:
(Actualizado 29/04/2015)

2 comentarios:

  1. Muy bueno el post, Carlos. Se sale.

    Con la opción "-O3" de GCC se hace la optimización TCO.

    ResponderEliminar
    Respuestas
    1. Muchas gracias Avelino, y muy buena aportación, yo no investigué si algún compilador de C/C++ lo soportaba

      Eliminar