Wie kann ich die Rekursionstiefe verfolgen?

Question

Ich habe eine rekursive Funktion, die ich Fehlerbehebung bin. Ich möchte die Rekursionstiefe ausgeben... d.h. wie oft die Funktion sich selbst aufruft.

Wenn ich eine statische Variable verwende, die am Anfang der Funktion inkrementiert und am Ende dekrementiert.

Kann ich damit die Tiefenstufe genau bestimmen?

recurse()
  {
  static int depth = 0;
  depth++;
  /*
  do stuff
  recurse()
  */
  depth--;
  return return_value;
  }

Answer 1

recurse(int depth = 0){
    ....
    recurse(depth+1);
}

Answer 2

Um es einfacher zu machen und

• Ausnahme Sicherer
• Gewinde Sicherer
• Unterstützung Baumrekursion (!)

_{Wenn Sie Ihre Vorstellungskraft wirklich ausreizen, könnte dies es dem Compiler erleichtern, einige rekursive Aufrufe zu inlinen und/oder eine Tail-Call-Optimierung im Falle einer Tail-Rekursion durchzuführen. <em>Ich habe keine Beweise dafür, dass dies eine Rolle spielt. </em>aber ich kann mir vorstellen, dass die Verwendung externer Symbole innerhalb eines Funktionskörpers die Compileroptimierung beeinflusst.}

Ich schlage vor:

stuff recurse(int level=0)
{

     //...
     recurse(level+1);

     //... (return stuff?)
     //... (throw exceptions?)

     //...
     recurse(level+1);

     //... (return stuff?)

}

Answer 3

Nein, das ist nicht der Fall, wenn eine Ausnahme ausgelöst wird. Eine bessere (und häufigere) Option ist:

int recurse(int depth=0)
{
    recurse(depth+1)
    return return_value;
}

Answer 4

Wenn Sie dies auf nicht-intrusive Weise tun möchten, können Sie Ihren Compiler bitten, jeden Aufruf für Sie zu instrumentieren, z.B. mit gcc:

#include <iostream>
static __thread int depth=-1;
extern "C" {
    void __cyg_profile_func_enter (void *, void *) __attribute__((no_instrument_function));
    void __cyg_profile_func_exit (void *, void *) __attribute__((no_instrument_function));
    void __cyg_profile_func_enter (void *func,  void *caller)
    {
        depth++;
    }

    void __cyg_profile_func_exit (void *func, void *caller)
    {
        depth--;
    }
}

class Foo {
public:
    void bar() {
        std::cout << "bar: " << depth << std::endl;
    }
};

int main() {
    Foo f;
    f.bar();
    return 0;
}

Sie müssen kompilieren mit -finstrument-functions damit dies funktioniert.

Answer 5

Im Allgemeinen möchten Sie eine Tiefenvariable inkrementieren, die außerhalb der rekursiven Funktion definiert ist, um die Threadsicherheit zu gewährleisten und sie von außerhalb der Funktion zu drucken.

Hier ist ein einfaches faktorielles Beispiel, das dies veranschaulicht:

#include <stdio.h>

unsigned factorial(unsigned x, unsigned* depth)
{
  if (x <= 1)
    return 1;

  ++*depth;

  return x * factorial(x - 1, depth);
}

int main(void)
{
  unsigned depth, f;

  depth = 0; f = factorial(1, &depth);
  printf("factorial=%u, depth=%u\n", f, depth);

  depth = 0; f = factorial(2, &depth);
  printf("factorial=%u, depth=%u\n", f, depth);

  depth = 0; f = factorial(6, &depth);
  printf("factorial=%u, depth=%u\n", f, depth);

  return 0;
}

Salida:

C:\>recdep.exe
factorial=1, depth=0
factorial=2, depth=1
factorial=720, depth=5