Solución:
Aunque a menudo ve lo siguiente como un ejemplo de conversión de factorial en tail-call:
int factorial(int n, int acc=1) {
if (n <= 1) return acc;
else return factorial(n-1, n*acc);
}
no es del todo correcto, ya que requiere que la multiplicación sea tanto asociativa como conmutativa. (Multiplicación es asociativo y conmutativo, pero lo anterior no sirve como modelo para otras operaciones que no satisfacen esas restricciones). Una mejor solución podría ser:
int factorial(int n, int k=1, int acc=1) {
if (n == 0) return acc;
else return factorial(n-1, k+1, acc*k);
}
Esto también sirve como modelo para la transformada de fibonacci:
int fibonacci(int n, int a=1, int b=0) {
if (n == 0) return a;
else return fibonacci(n-1, a+b, a);
}
Tenga en cuenta que estos calculan la secuencia comenzando por el principio, en lugar de poner en cola las continuaciones pendientes en una pila de llamadas. Por lo tanto, estructuralmente se parecen más a la solución iterativa que a la solución recursiva. Sin embargo, a diferencia del programa iterativo, nunca modifican ninguna variable; todas las uniones son constantes. Ésta es una propiedad interesante y útil; en estos casos simples no hay mucha diferencia, pero escribir código sin reasignaciones facilita algunas optimizaciones del compilador.
De todos modos, el último proporciona un modelo para su función recursiva; como la secuencia de fibonacci, necesitamos mantener los valores pasados relevantes, pero necesitamos tres de ellos en lugar de dos:
int mouse(int n, int a=1, int b=1, int c=1) {
if (n <=2 ) return a;
else return mouse(n-1, a*c+1, a, b);
}
Adenda
En los comentarios se plantearon dos preguntas. Intentaré responderlas (y una más) aquí.
Primero, debe quedar claro (considerando la arquitectura de la máquina subyacente que no tiene el concepto de llamada de función) que cualquier llamada de función puede reformularse como un goto (posiblemente con almacenamiento intermedio no acotado); además, cualquier goto se puede expresar como una llamada de cola. Por lo tanto, es posible (pero no necesariamente bonito) reescribir cualquier recursividad como recursividad de cola.
El mecanismo habitual es el “estilo de paso de continuación”, que es una forma elegante de decir que cada vez que desea llamar a una función, empaqueta el resto de la función actual como una nueva función (la “continuación”) y la pasa continuación a la función llamada. Dado que cada función recibe una continuación como argumento, tiene que finalizar cualquier continuación que cree con una llamada a la continuación que recibió.
Eso es probablemente suficiente para hacer que su cabeza dé vueltas, así que lo pondré de otra manera: en lugar de presionar argumentos y una ubicación de retorno en la pila y llamar a una función (que luego regresará), usted inserta argumentos y una ubicación de continuación en la pila. e ir a una función, que luego irá a la ubicación de continuación. En resumen, simplemente convierte la pila en un parámetro explícito, y luego nunca necesita regresar. Este estilo de programación es común en el código impulsado por eventos (consulte Python Twisted), y es un verdadero dolor de cabeza escribir (y leer). Por lo tanto, recomiendo encarecidamente dejar que los compiladores realicen esta transformación por usted, si puede encontrar uno que lo haga.
@xxmouse sugirió que saqué la ecuación de recursividad de un sombrero y pregunté cómo se derivaba. Es simplemente la recursividad original, pero reformulada como una transformación de una sola tupla:
fn = fn-1*fn-3 + 1
=>
Fn = <Fn-11*Fn-13+1, Fn-11, Fn-12>
No sé si eso está más claro, pero es lo mejor que puedo hacer. Mire el ejemplo de Fibonacci para ver un caso un poco más simple.
@j_random_hacker pregunta cuáles son los límites de esta transformación. Funciona para una secuencia recursiva donde cada elemento puede expresarse mediante alguna fórmula de la anterior. k elementos, donde k es una constante. Hay otras formas de producir una recursividad de llamada de cola. Por ejemplo:
// For didactic purposes only
bool is_odd(int n) { return n%2 == 1; }
int power(int x, int n, int acc=1) {
if (n == 0) return acc;
else if (is_odd(n)) return power(x, n-1, acc*x);
else return power(x*x, n/2, acc);
}
Lo de arriba es no lo mismo que la recursividad habitual sin llamada final, que realiza una secuencia de multiplicaciones diferente (pero equivalente e igualmente larga).
int squared(n) { return n * n; }
int power(int x, int n) {
if (n == 0) return 1;
else if (is_odd(n)) return x * power(x, n-1));
else return squared(power(x, n/2));
}
Gracias a Alexey Frunze por la siguiente prueba: Salida (ideone):
mouse(0) = 1
mouse(1) = 1
mouse(2) = 1
mouse(3) = 2
mouse(4) = 3
mouse(5) = 4
mouse(6) = 9
mouse(7) = 28
mouse(8) = 113
mouse(9) = 1018
Usando Google, encontré esta página que describe Tail Recursion. Básicamente, necesita dividir la función en al menos otras dos funciones: una que hace el trabajo, manteniendo una “acumulación” del valor actual, y otra que es un controlador para su función de workhouse. El ejemplo factorial en C está a continuación:
/* not tail recursive */
unsigned int
factorial1(unsigned int n)
{
if(n == 0)
return 1;
return n * factorial1(n-1);
}
/* tail recursive version */
unsigned int
factorial_driver(unsigned int n, unsigned int acc)
{
if(n == 0)
return acc;
/* notice that the multiplication happens in the function call */
return factorial_driver(n - 1, n * acc);
}
/* driver function for tail recursive factorial */
unsigned int
factorial2(unsigned int n)
{
return factorial_driver(n, 1);
}
La respuesta de @Alexey Frunze está bien, pero no es exactamente correcta. De hecho, es posible convertir cualquier programa en uno en el que toda recursividad sea recursividad de cola transformándolo en Continuation Passing Style.
No tengo tiempo en este momento, pero intentaré volver a implementar su programa en CPS si tengo algunos minutos.