c++ - 最小化递归函数中的变量拷贝

Question

在处理递归函数时，我正在寻找有效的内存分配。据我所知，我在函数中使用的变量将在内存中保持分配状态，直到递归完成。有没有办法避免这种情况，因为我相信这会导致我的代码运行缓慢，每次调用函数时都会复制状态变量(如果我错了，请纠正我，因为我是 C++ 新手)。

#include <fstream>
#include <vector>
using namespace std;

int N = 30;
double MIN_COST = 1000000;
vector<int> MIN_CUT = {};


void minCut(vector<int> state, int index, int nodeValue) {
    double currentCost;

    if (index >= 0) {
        currentCost = getCurrentCost(state); // some magic evaluating state cost
        state.push_back(nodeValue);
        if (currentCost >= MIN_COST) {    // kill branch if incomplete solution is already worse than best achieved solution
            return;
        }
    }

    if (index == N - 1) {   // check if leaf node
        if (currentCost < MIN_COST) {
            MIN_COST = currentCost;
            MIN_CUT = state;
        }
        return;
    }

    minCut(state, index + 1, 1); // left subtree - adding 1 to vector
    minCut(state, index + 1, 0); // right subtree - adding 0 to vector

    return;
}


int main() {
    vector<int> state = {};
    minCut(state, -1, NULL);

    cout << MIN_COST << "\n";
    return 0;
}

Answer 1

您的算法正在有效地构建路径树，但您使用的是 vector保存每条路径的节点。

           A
         /   \
        /     \
       B       C
      / \     / \
     D   E   F   G

这是你正在遍历的树。

但是您正在每个节点创建新 vector ，其中包含到该节点的整个路径。所以当你访问节点 G , 在你的堆栈中你有 3 vector s:

vector { A, C, G }
vector { A, C }
vector { A }

正如您所注意到的那样，这应该很清楚，但也许以这种方式看到它暗示了正确的高效实现。

调用堆栈本身保存到根节点的路径。访问时的堆栈 G会像

minCut < visiting G >
minCut < visiting C >
minCut < visiting A >

为了有效地利用这一事实，制作 minCut传递最少的信息。在这种情况下，我们谈论的是链表之类的东西。

然后你有两个选项跳出来:

使用 vector ， 但:

通过引用传递它。

然后您必须在调用、推送和弹出节点之间维护它以与实际状态保持同步。

使用实际的链表。构建 vector 应该很容易通过遍历指向父节点的指针。