Minimizing variable copies in recursive function

Question

I'm looking for efficient memory allocation when dealing with recursive function. As far as I understand, variables I use in the function will remain allocated in memory until recursion is finished. Is there a way to avoid this as I believe this causes slow run of my code below where state variable is copied every time the function is called (correct me if I'm wrong as I'm new to 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

Your algorithm is effectively building a tree of paths, but you're using a vector to hold the nodes for each path.

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

This is the tree you're traversing.

But you're creating new vectors at every node, which contain the whole path up to that node. So as you're visiting node G, in your stack you have 3 vectors:

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

It should be clear how this is less efficient as you have noticed, but maybe seeing it this way hints at the correct efficient implementation.

The call stack itself holds the path to the root node. The stack when visiting G would be something like

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

In order to efficiently exploit this fact, make minCut pass the minimum amount of information. In this case we're talking about something linked-list like.

You have then two options that jump out:

1. Use vector, but:
   1. Pass it by reference.
   2. And you must then maintain it across calls, pushing and popping nodes to keep synchronized with the actual state.
2. Use an actual linked list. It should be easy to construct the vector by traversing pointers-to-parent-nodes.

Answer 2

Yes, there is a more efficient way to pass state through each function call. This is called passing by reference and can be achieved like so:

void minCut(vector<int>& state, int index, int nodeValue) { ...

This will result in the original state being referenced instead of copied each time the function is called.

For this to work correctly in the code you posted you will have to make some modifications, this is just the general concept.