Come rilevare la chiamata ricorsiva di root?

Question

Dire che stiamo scrivendo una semplice funzione ricorsiva fib(n) che calcola l'ennesimo numero di Fibonacci. Ora, vogliamo che la funzione stampi l'ennesimo numero. Poiché la stessa funzione viene richiamata ripetutamente, deve essere presente una condizione che consenta solo la chiamata root a stampare. La domanda è: come scrivere questa condizione senza passare alcun argomento aggiuntivo, o usando variabili globali/statiche.

Così, abbiamo a che fare con qualcosa di simile:

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; 
} 

ho pensato che la chiamata radice differisce da tutti i bambini con il ritorno a un chiamante diverso, vale a dire il metodo principale in questo esempio. Volevo sapere se è possibile usare questa proprietà per scrivere la condizione e come.

Aggiornamento: si prega di notare che questo è un esempio inventato che serve solo a presentare l'idea. Questo dovrebbe essere chiaro dai tag. Non sto cercando soluzioni standard. Grazie.

Answer 1

Il modo in cui vorrei fare questo è con una funzione di supporto:

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; 
} 

In alternativa, si potrebbe scrivere in questo modo (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 chiamata ricorsiva di radice è il punto in cui la ricorsione viene invocata, ossia l'invocazione in main. Dato che, si potrebbe riscrivere il codice leggermente (qualcosa di simile):

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

Ecco un modo difficile, anche se non sono sicuro che ne vale 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; 
} 

Ma, il la funzione richiede che tu non intenda davvero mandare un valore negativo :).

Answer 4

Se davvero intenzione di chiedere se C ha accesso a una sorta di API che consente al codice in un corpo della funzione di scoprire da dove è stata chiamata la funzione di esecuzione, la risposta è no.

Answer 5

Penso che si possa ottenere l'indirizzo di ritorno dallo stack e confrontarlo in qualche modo con l'indirizzo della funzione fib. L'indirizzo di ritorno dovrebbe essere da qualche parte vicino al parametro n a meno che n non sia passato in qualche registro, ma in C standard non dovrebbe. Devi solo sapere dove l'indirizzo di ritorno è relativo al parametro.