Come posso trovare la profondità di una funzione ricorsiva in C++

Question

Come posso trovare la profondità corrente all'interno di una funzione ricorsiva in C++ senza passare al livello precedente? cioè è possibile sapere quante volte è stata chiamata la funzione senza utilizzare un parametro per tenere traccia del livello e passare quel numero come parametro ogni volta che viene chiamata la funzione?

Per esempio il mio funzione ricorsiva assomiglia a questo:

DoSomething(int level) 
{ 
    print level; 
    if (level > 10) 
    return; 
    DoSomething(++level); 
} 

main 
{ 
    DoSomething(0); 
} 

Answer 1

Costruire sulla risposta già data da JoshD:

void recursive() 
{ 
    static int calls = 0; 
    static int max_calls = 0; 
    calls++; 
    if (calls > max_calls) 
     max_calls = calls; 

    recursive(); 

    calls--; 
} 

Questo ripristina il contatore dopo la funzione ricorsiva è completa, ma segue ancora la profondità massima di ricorsione.

Non userei variabili statiche come questa per niente tranne un test rapido, da eliminare subito dopo. Se hai davvero bisogno di rintracciarlo continuamente, ci sono metodi migliori.

Answer 2

è possibile utilizzare una variabile statica locale, se non si cura di thread-safe.

Anche se questo ti darà un conteggio corretto solo la prima volta che esegui la tua routine ricorsiva. Una tecnica migliore sarebbe una classe di tipo di guardia RAII che contiene una variabile statica interna. All'inizio della routine ricorsiva, costruisci la classe di guardia. Il costruttore incrementerebbe la variabile statica interna e il distruttore lo decrementerebbe. In questo modo, quando crei un nuovo stack-frame il contatore aumenta di uno, e quando ritorni da ogni stack-frame il contatore decrementa di uno.

struct recursion_guard 
{ 
    recursion_guard() { ++counter; } 

    ~recursion_guard() { --counter; } 

    static int counter; 
}; 

int recursion_guard::counter = 0; 

void recurse(int x) 
{ 
    recursion_guard rg; 
    if (x > 10) return; 
    recurse(x + 1); 
} 

int main() 
{ 
    recurse(0); 
    recurse(0); 
} 

Si noti tuttavia che questo non è ancora sicuro per i thread. Se è necessaria la sicurezza del thread, è possibile sostituire la variabile di archiviazione statica con una variabile di archiviazione locale del thread, utilizzando le strutture locali del thread 0xo C++ 0x.

Answer 3

Si potrebbe utilizzare una variabile statica nella funzione ...

void recursive() 
{ 
static int calls = 0; 
calls++; 
recursive(); 
} 

Naturalmente, questo manterrà il conteggio quando si avvia una nuova chiamata originario ....

Answer 4

convertire level in una variabile di istanza di un nuovo oggetto (in genere un modello) in grado di contenere gli argomenti e (eventualmente) la funzione. allora puoi riutilizzare l'interfaccia dell'accumulatore di ricorsione.

Answer 5

Si può anche provare a utilizzare una variabile globale per registrare la profondità.

var depth = 0; 

DoSomething() 
{ 
    print ++depth; 
    if (depth > 10) 
    return; 
    DoSomething(); 
} 

main 
{ 
    DoSomething(0); 
} 

Answer 6

È possibile anche passare il livello come parametro modello, se è possibile determinarlo in fase di compilazione. Puoi anche usare un oggetto funzione. Questa è di gran lunga la migliore opzione - meno problemi, e le variabili statiche dovrebbero essere evitate ovunque possibile.

struct DoSomething { 
    DoSomething() { 
     calls = 0; 
    } 
    void operator()() { 
     std::cout << calls; 
     calls++; 
     if (calls < 10) 
      return operator()(); 
     return; 
    } 
    int calls; 
}; 

int main() { 
    DoSomething()(); // note the double(). 
    std::cin.get(); 
} 

Answer 7

Se si vuole che sia rientrante e thread-safe, perché non:

void rec(int &level) // reference to your level var 
{ 
    // do work 

    rec(++level); // go down one level 
} 

main() 
{ 
    //and you call it like 
    int level=0; 
    rec(level); 

    cout<<level<<" levels."<<endl; 
} 

Nessun variabili statiche/globali di rovinare la filettatura ed è possibile utilizzare diverse variabili per i diversi catene ricorsive per problemi di re-entrancy.