¿Cómo reconocer qué es y qué no es recursividad final?

Question

A veces es lo suficientemente simple (si la auto llamada es la última declaración, es recursividad final), pero todavía hay casos que me confunden. Un profesor me dijo que "si no hay instrucciones para ejecutar después de la auto-llamada, es la recursividad de la cola". ¿Qué hay de estos ejemplos (sin tener en cuenta el hecho de que no tienen mucho sentido):

a) Éste debe ser recursivo de cola, viendo cómo la auto-llamada es la última instrucción, y no queda nada para ejecutar después de ella .

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else 
     return foo(n-2); 
} 

b) ¿Pero qué tal este? Debería ser una llamada de cola, porque si la condición es verdadera, nada más que se ejecutará, pero ¿no es la última declaración?

function foo(n) 
{ 
    if(n != 0) 
     return foo(n-2); 
    else 
     return 0; 
} 

c) ¿Qué tal este? En ambos casos, la auto llamada será la última cosa ejecutada:

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else  
    { 
     if(n > 100) 
      return foo(n - 2); 
     else 
      return foo(n - 1); 
    } 
} 

Answer 1

Podría ayudarlo a pensar sobre esto en términos de cómo se implementan realmente las optimizaciones de cola. Eso no es parte de la definición, por supuesto, pero sí motiva la definición.

Normalmente, cuando se invoca una función, el código de llamada almacenará los valores de registro que necesitará más adelante, en la pila. También almacenará una dirección de retorno, que indica la siguiente instrucción después de la llamada. Hará lo que sea necesario para asegurarse de que el puntero de pila esté configurado correctamente para el destinatario. Luego saltará a la dirección de destino [*] (en este caso, la misma función). A su regreso, sabe que el valor de retorno está en el lugar especificado por la convención de llamadas (registro o ranura de pila).

Para una llamada de cola, la persona que llama no hace esto. Ignora cualquier valor de registro, porque sabe que no lo necesitará más adelante. Configura el puntero de la pila para que el destinatario use la misma pila que la persona que llama, y ​​no se configura como la dirección de retorno, simplemente salta a la dirección de destino.Por lo tanto, el destinatario sobrescribirá la misma región de pila, colocará su valor de retorno en la misma ubicación en que la persona que llama habría puesto su valor de retorno, y cuando vuelva, no regresará a su llamador, sino que regresará a su llamador llamador.

Por lo tanto, informalmente, una función es recursiva de cola cuando es posible que ocurra una optimización de cola de cola, y cuando el objetivo de la llamada de cola es la función misma. El efecto es más o menos el mismo que si la función contuviera un bucle, y en lugar de llamarse a sí mismo, la llamada de cola salta al inicio del bucle. Esto significa que no debe haber variables necesarias después de la llamada (y de hecho no hay "trabajo por hacer", que en un lenguaje como C++ no significa nada que destruir), y el llamador debe devolver el valor de retorno de la llamada final.

Esto es todo para recursión de cola simple/trivial. Hay transformaciones que pueden utilizarse para hacer algo recursivo que aún no lo es, por ejemplo, la introducción de parámetros adicionales, que almacenan cierta información utilizada por el nivel inferior de recursión, para hacer un trabajo que de otro modo se realizaría en el camino de salida". Así, por ejemplo:

int triangle(int n) { 
    if (n == 0) return 0; 
    return n + triangle(n-1); 
} 

se pueden hacer recursiva de cola, ya sea por el programador o automáticamente por un compilador lo suficientemente inteligente, así:

int triangle(int n, int accumulator = 0) { 
    if (n == 0) return accumulator; 
    return triangle(n-1, accumulator + n); 
} 

Por lo tanto, la primera función podría ser descrito como " cola recursiva "por alguien que está hablando de un lenguaje/compilador suficientemente inteligente. Prepárate para esa variante de uso.

[*] Almacenar una dirección de retorno, mover el puntero de la pila y saltar, puede o no estar envuelto en un solo código de operación por la arquitectura, pero incluso si no es lo que ocurre normalmente.

Answer 2

Yep; Creo que su profesor quiso decir que en cualquier camino, si la instrucción final es recursiva, entonces es recursividad final.

Por lo tanto, los tres ejemplos son recursivos de cola.

Answer 3

Todas sus funciones son recursivas de cola.

ninguna instrucción izquierda después de la auto-llaman

significa: Después de la auto-llamada, regrese de la función, es decir, no más código tiene que ser ejecutado, y no es que haya no más líneas de código en la función.

Answer 4

Los tres ejemplos son cola recursiva. En términos generales, es recursividad de cola, si el resultado de la función (la expresión que sigue a la palabra clave "devolver") es una llamada solitaria a la función en sí misma. Ningún otro operador debe estar involucrado en el nivel más externo de la expresión. Si la llamada a sí mismo es solo una parte de una expresión, entonces la máquina debe ejecutar la llamada, pero luego debe volver a la evaluación de dicha expresión, es decir, no fue al final de la ejecución de la función, sino a la mitad de una expresión. Sin embargo, esto no se aplica a ningún parámetro que pueda tomar la llamada recursiva: todo está permitido allí, incluidas las llamadas recursivas a sí mismo (por ejemplo, "return foo (foo (0));"). La optimización de llamadas a saltos solo es posible para la llamada externa, por supuesto.