C++ Recursion Function to Iterative Function

Question

I have been having some problems with this, as it causes a stack overflow:

unordered_set<string> seen;
vector<long long> edges;

void dfs(string node, long long& k, string& A) //used by deBruijn function
{
    for (long long i = 0; i < k; i = i + 1) {
        string str = node + A[i];
        if (!seen.count(str)) {
            seen.insert(str);
            dfs(str.substr(1), k, A); //<-Call the recursion
            edges.push_back(i);
        }
    }
}

string deBruijn(long long n, long long k, string A) //Calls the recursive dfs
{
    seen.clear();
    edges.clear();
    string startingNode = string(n - 1, A[0]);
    dfs(startingNode, k, A);
    string S; 
    long long l = pow(k, n);
    for (long long i = 0; i < l; i = i + 1)
        S += A[edges[i]];
    S += startingNode;
    return S;
}

How can I turn the "dfs" function into an iterative function?

Visual Studio will tell you exactly where it crashes. Walk up the callstack to your project code after the exception. — drescherjm, Oct 04 '19 at 18:13
Visual Studio will tell you that you have a stack overflow, meaning your recursive function just kept calling itself without returning. You need to start reading and reporting your error messages, since this is important information you left out. — PaulMcKenzie, Oct 04 '19 at 18:17
When debugging there should be a stack frame combobox on the top tool bar and also a call stack window. — drescherjm, Oct 04 '19 at 18:24
@EricPetersen When VS crashes, there is a call stack window. In there are all of the functions that were called that led to the crash. It has nothing to do with compilation. You will see in the call stack a massive list of calls to `dfs`, all waiting for their `return` to happen. — PaulMcKenzie, Oct 04 '19 at 18:24
You may have to change the recursive algorithm to an iterative one possibly using this: [https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration](https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) — drescherjm, Oct 04 '19 at 19:06

C++ Recursion Function to Iterative Function

0 Answers0