¿Cómo detectar la llamada recursiva raíz?

Question

Supongamos que estamos escribiendo una función recursiva simple fib(n) que calcula el enésimo número de Fibonacci. Ahora, queremos que la función imprima ese enésimo número. Como se está llamando repetidamente a la misma función, tiene que haber una condición que permita solo imprimir la llamada raíz. La pregunta es: cómo escribir esta condición sin pasar ningún argumento adicional, o usar variables globales/estáticas.

Por lo tanto, estamos tratando con algo como esto:

int fib(int n) { 
    if(n <= 0) return 0; 
    int fn = 1; 
    if(n > 2) fn = fib(n-2) + fib(n-1); 
    if(???) cout << fn << endl; 
    return fn; 
} 

int main() { 
    fib(5); 
    return 0; 
} 

pensé que la llamada raíz difiere de todos los niños antes de regresar a una persona que llama diferente, a saber, el método principal en este ejemplo. Quería saber si es posible usar esta propiedad para escribir la condición y cómo.

Actualización: tenga en cuenta que este es un ejemplo artificial que solo sirve para presentar la idea. Esto debería quedar claro a partir de las etiquetas. No estoy buscando soluciones estándar. Gracias.

Answer 1

La manera Me gustaría hacer esto es con una función de ayuda:

int _fib(int n) { 
    if(n <= 0) return 0; 
    int fn = 1; 
    if(n > 2) fn = _fib(n-2) + _fib(n-1); 
    return fn; 
} 

int fib(int n) { 
    int fn=_fib(n); 
    cout << fn << endl; 
    return fn; 
} 

Alternativamente, se podría escribir como este (C++):

int fib(int n, bool f=true) { 
    if(n <= 0) return 0; 
    int fn = 1; 
    if(n > 2) fn = fib(n-2, false) + fib(n-1, false); 
    if(f) cout << fn << endl; 
    return fn; 
} 

Answer 2

La llamada recursiva raíz es el punto en el que se invoca la recursión, es decir, la invocación en main. Teniendo en cuenta que, se podría reescribir el código ligeramente (algo así):

int fib(int n) { 
    if(n <= 0) return 0; 
    int fn = 1; 
    if(n > 2) fn = fib(n-2) + fib(n-1); 
    return fn; 
} 

int main() { 
    cout << fib(5) << endl; 
    return 0; 
} 

Answer 3

Aquí llega un camino difícil, aunque no estoy seguro de que es la pena :):

int fib(int n) { 
// if(n <= 0) return 0; 
    int isRoot; 
    if (n <= 0){ 
     isRoot = 1; 
     n = -n; 
    } 
    else isRoot = 0; 
    int fn = 1; 
    if(n > 2) fn = fib(n-2) + fib(n-1); 
    if(isRoot) cout << fn << endl; 
    return fn; 
} 

int main() { 
    fib(-5); 
    return 0; 
} 

embargo, la la función requiere que no quieras decir realmente enviar un valor negativo :).

Answer 4

Si usted realmente quiere decir preguntar si C tiene acceso a algún tipo de API que permite que el código en un cuerpo de función descubra desde donde se llamó a la función de ejecución, la respuesta es no.

Answer 5

Creo que podría obtener la dirección de retorno de la pila y compararla de algún modo con la dirección de la función fib. La dirección de retorno debe estar cerca del parámetro n a menos que n se pase en algún registro, pero en C estándar no debería. Solo tiene que saber dónde está la dirección de retorno en relación con el parámetro.