Как я могу найти глубину рекурсивной функции в C ++

Question

Как найти текущую глубину внутри рекурсивной функции в C ++, не переходя на предыдущий уровень? можно ли узнать, сколько раз была вызвана функция без использования параметра для отслеживания уровня и передачи этого числа в качестве параметра при каждом вызове функции?

Например, моя рекурсивная функция выглядит так:

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

main
{
  DoSomething(0);
}

Answer 1

Опираясь на уже полученный ответ JoshD :

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

    recursive();

    calls--;
}

Сбрасывает счетчик после завершения рекурсивной функции, но все равно отслеживает максимальную глубину рекурсии.

Я бы не стал использовать подобные статические переменные ни для чего, кроме быстрого теста, который вскоре будет удален. Если вам действительно нужно отслеживать это на постоянной основе, есть лучшие методы.

Answer 2

Вы можете использовать статическую переменную в функции ...

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

Конечно, она будет продолжать отсчитываться, когда вы начнете новый исходящий вызов ....

Answer 3

Если вы хотите, чтобы он был входящим и потокобезопасным, почему бы и нет:

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

Нет статических / глобальных переменных , чтобы испортить потоки, и вы можете использовать разные переменные для разных рекурсивных цепочек для проблем с повторным входом.

Answer 4

Вы можете использовать локальную статическую переменную, если вас не волнует безопасность потоков.

Хотя, это даст вам правильный счет только при первом запуске вашей рекурсивной программы. Лучшим методом будет класс защиты типа RAII, который содержит внутреннюю статическую переменную. В начале рекурсивной процедуры создайте класс защиты. Конструктор будет увеличивать внутреннюю статическую переменную, а деструктор уменьшать ее. Таким образом, при создании нового стекового кадра счетчик увеличивается на единицу, а при возврате из каждого стекового кадра счетчик уменьшается на единицу.

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

Обратите внимание, что это все еще не потокобезопасно. Если вам нужна безопасность потоков, вы можете заменить переменную static-storage на переменную thread-local-storage, используя boost::thread_specific_ptr или локальные средства потока C ++ 0x.

Answer 5

Вы также можете передать уровень в качестве параметра шаблона, если он может быть определен во время компиляции. Вы также можете использовать функциональный объект. Это, безусловно, лучший вариант - меньше хлопот, и по возможности следует избегать статических переменных.

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 6

Вы также можете попробовать использовать глобальную переменную для записи глубины.

var depth = 0;

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

main
{
  DoSomething(0);
}

Answer 7

преобразовать level в переменную экземпляра нового объекта (обычно шаблона), способного содержать аргументы и (возможно) функцию. затем вы можете повторно использовать интерфейс рекурсивного аккумулятора.