ведение счета рекурсии

Question

Я пытаюсь подсчитать количество вызовов в рекурсивной функции перестановки.

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

В конечном итоге мне бы хотелось, чтобы функция возвращала подмножество перестановок, заданных аргументами lbound и ubound, и для этого я думаю, что мне нужно каким-то образом вести внутренний подсчет.

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

Для этого кода я бы хотел, чтобы счет возвращался как 100.

#include <vector>
#include <iostream>;

using namespace std;

int& Permutations(vector<vector<int>> param, vector<vector<int>> &perm, int index=0)
{
    static vector<int> iter;
    static int count = 0;

    if (index == param.size())
    {
        perm.push_back(iter);   // add permutation to queue
        count++;
        return count;
    }

    for (int i=param[index][0]; i<=param[index][1]; i+=param[index][2])
    {
        if (iter.size() > index) iter[index] = i;
        else iter.push_back(i);
        Permutations(param, perm, index+1); // recursive function
    }
}

void main()
{
    vector<vector<int>> params; // vector of parameter vectors

    vector<int> param1, param2;

    int arr1[3] = {0,9,1};  // range for each parameter vector
    int arr2[3] = {0,9,1};  // specified as lbound, ubound, step

    param1.insert(param1.end(),arr1,arr1+3);
    param2.insert(param2.end(),arr2,arr2+3);

    params.push_back(param1);
    params.push_back(param2);

    vector<vector<int>> queue;  // queue of generated permutations

    int permcount = Permutations(params,queue);

    cout << "the permutation count is " << permcount << endl;
    cin.get();
}

Answer 1

Использование счетчика static не будет работать, потому что он никогда не будет сброшен (и вызовет проблемы, если вы когда-либо будете использовать многопоточность).

Вместо этого, как насчет этого:

int Permutation(/* params */)
{
    int count = 1;  // Count ourself

    for (whatever)
    {
        count += Permutation(whatever);  // Count cumulative sum from recursion
    }

    return count;
}

Каждый вызов Permutation() возвращает общее количество вызовов, которые были сделаны ниже , это в дереве вызовов.Когда мы раскручиваемся, все подсчеты поддеревьев суммируются, чтобы в конечном итоге получить окончательное возвращаемое значение.

Answer 2

int foo(int count,/*Other Params*/) {
/*Calucation*/
 if (!terminatingCondition) {
  foo(count++,/*Other Params*/);
 }
 logger.log("foo was called " + count + "times");
 return /*calcualtion*/;
}

Answer 3

Я просто пытаюсь ответить на вопрос, игнорируя вашу реальную цель алгоритма.Две статики должны быть перемещены в ссылки на аргументы, или у вас нет хорошего способа сбросить их значения.

void Permutations(vector<vector<int>> param, vector<vector<int>> &perm, vector<int> &iter, int &count, int index=0)
{
    ++count;
    // ...
}