Tail Recursion
Un poco de cerveza negra y el estar de vacaciones logran cosas muy locas. Hablando con un amigo de optimizaciones (correccion: el me hablaba a mi...), se me ocurrio escribir una version recursiva de factorial que a los compiladores modernos les guste:
C:
-
double fact( double n )
-
{
-
if ( n> 0.0 )
-
return n * fact( n - 1 );
-
else
-
return 1;
-
}
-
-
double fact_tail( double n, double nant )
-
{
-
if ( n> 0.0 )
-
return fact_tail( n - 1, nant * n );
-
else
-
return nant;
-
}
-
-
double fact2(double n)
-
{
-
return fact_tail(n, 1);
-
}
La funcion fact es la version clasica que aprendes en primer año de la facultad, y la funcion fact2 se le conoce como una funcion de recursion por cola. Estas llamadas recursivas son eficientes por naturaleza, facil de implementarlas con un simple while. Los pocos experimentos que Hernan realizo indican que Visual C++ 2005 detecta y compila eficientemente dichas funciones.
December 18th, 2006 at 22:06
Hago la aclaración de que SOLO fact_tail VC 2005 la implementa como iterativa, fact la hace recursiva como es habitual.
fact2 no la implementa, todas las llamadas a fact2 son pasadas a fact_tail(n, 1) directamente y por lo tanto fact2 jamas es llamada.