¿Cómo puedo encontrar la profundidad de una función recursiva en C++

Question

¿Cómo puedo encontrar la profundidad actual dentro de una función recursiva en C++ sin pasar al nivel anterior? es decir, ¿es posible saber cuántas veces se llamó a la función sin usar un parámetro para hacer un seguimiento del nivel y pasar ese número como un parámetro cada vez que se llama a la función?

Por ejemplo, mi función recursiva se parece a esto:

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

main 
{ 
    DoSomething(0); 
} 

Answer 1

Sobre la base de la respuesta ya dado por JoshD:

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

    recursive(); 

    calls--; 
} 

Esto restablece el contador después de la función recursiva es completa, pero todavía un seguimiento de la profundidad máxima de la recursión.

No utilizaría variables estáticas como esta para nada que no sea una prueba rápida, que se eliminará poco después. Si realmente necesita hacer un seguimiento de esto en forma permanente, existen mejores métodos.

Answer 2

Usted puede utilizar una variable estática local, si no se preocupan por la seguridad de rosca.

Aunque esto solo le dará un recuento correcto la primera vez que ejecute su rutina recursiva. Una técnica mejor sería una clase RAII tipo guardia que contiene una variable estática interna. Al comienzo de la rutina recursiva, construye la clase de guardia. El constructor incrementaría la variable estática interna, y el destructor la disminuiría. De esta manera, cuando creas un nuevo marco de pila, el contador se incrementa en uno, y cuando regresas de cada marco de pila, el contador disminuiría en 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); 
} 

Sin embargo, tenga en cuenta que esto todavía no es seguro para subprocesos. Si necesita seguridad de subprocesos, puede reemplazar la variable de almacenamiento estático con una variable de almacenamiento local de subprocesos, ya sea utilizando boost::thread_specific_ptr o las instalaciones locales de subprocesamiento C++ 0x.

Answer 3

Se puede usar una variable estática en la función ...

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

Por supuesto, esto mantendrá el recuento cuando se inicia una nueva llamada de origen ....

Answer 4

convierte level a una variable de instancia de un nuevo objeto (generalmente una plantilla) capaz de contener los argumentos y (posiblemente) la función. entonces puedes reutilizar la interfaz del acumulador de recursividad.

Answer 5

También puede intentar usar una variable global para registrar la profundidad.

var depth = 0; 

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

main 
{ 
    DoSomething(0); 
} 

Answer 6

También puede pasar el nivel como un parámetro de plantilla, si se puede determinar en tiempo de compilación. También podría usar un objeto de función. Esta es, de lejos, la mejor opción: menos molestias, y las variables estáticas deben evitarse siempre que sea posible.

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

Si usted quiere que sean reentrantes y seguro para subprocesos, por qué no:

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

No/variables globales estáticas a desordenar roscado y se pueden utilizar diferentes variables para diferentes cadenas recursivas para problemas de reentrada.