C++: How passed variable in recursive function call behaves? Conditions to correctly modify it?

Question

Could anyone please let me know why the following code in c++ doesn't work?

// count number of ways to construct a target string from a given set of strings
#include "bits/stdc++.h"

using namespace std;

int countConstruct(string target, vector < string > wordBank, map < string, int > memo = {})
{
  if (memo.find(target) != memo.end())
    return memo.at(target);

  if (target == "")
    return 1;

  int totalCount = 0;

  for (auto word: wordBank)
  {
    if (target.find(word) == 0)
    {
      auto suffix = target.substr(word.length(), target.length() - word.length());

      int numWaysForRest = countConstruct(suffix, wordBank, memo);

      totalCount += numWaysForRest;
    }
  }

  memo[target] = totalCount;

  return totalCount;
}

int main(int argc, char * argv[])
{
  cout << boolalpha;

  cout << countConstruct("abcdef", { "ab", "abc", "cd", "def", "abcd", "ef" }) << endl;

  cout << countConstruct("skateboard", { "bo", "ska", "ate", "sk", "boar" }) << endl;

  cout << countConstruct(
    "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee", 
    { "e", "eee", "eeee", "eeeee", "eeeeee", "eeeeeee" }) 
    << endl;

  return 0;
}

where as it JavaScript counterpart does:

// count number of ways the target string can be constructed from a given set of strings

const countConstruct = (target, wordBank, memo = {}) => {
  if (target in memo) return memo[target];

  if (target === '') return 1;

  let totalCount = 0;

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const numWaysToRest = countConstruct(target.slice(word.length), wordBank, memo);

      totalCount += numWaysToRest;
    }
  }

  memo[target] = totalCount;

  return totalCount;
}

console.log(countConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd", "ef"]));

console.log(countConstruct("skateboard", ["bo", "ska", "ate", "sk", "boar"]));

console.log(countConstruct("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee", ["e", "eee", "eeee", "eeeee", "eeeeee", "eeeeeee"]));

In the above C++ code if I make the "memo" variable static the program works. Can anyone tell me how to make the program work without making it static and through recursion only? What is internals behind these?

1) Any source that teaches `#include "bits/stdc++.h"` should be avoided as much as possible. [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) 2) Did you try to debug your program to see what's happening? — Evg, Apr 05 '21 at 12:59
@Evg 1. I do understand cons of bits/stdc++.h, but as a competitive programmer, In current context, I need to focus more on coding, so I need libraries availability at ease. 2. I did debug the code and found that memo variable doesn't get updated as expected. — hbkvikas, Apr 05 '21 at 13:33
I wouldn't want to visit a competitive doctor or fly with a competitive pilot... — Evg, Apr 05 '21 at 14:10

score 0 · Answer 1 · answered Apr 05 '21 at 13:14

To clarify, the goal of the program is to make this function memoized to speed up recursive functions, right? And the problem is that the third test case (with a string with a ton of 'e's), doesn't seem to finish?

If so, the problem is in the countConstruct declaration.
int countConstruct(string target, vector<string> wordBank, map<string, int> memo = {})

memo is a map<string, int> type variable, C++ creates a copy of the map every recursive call. That copy can get really expensive over many recurisve calls as the map grows bigger. It worked with a static memo variable because there wasn't a copy being made every time there was a recursive call.

One way to fix it, is to declare memo as a reference: int countConstruct(string target, vector<string> wordBank, map<string, int>& memo)

This way, instead of making a copy of the map every recursive call, the function just takes a reference to the already existing map. References are very cheap!

The downside here is that you can no longer have a default value for the memo arg, and you'll have to explicitly pass in an argument every time you call the function from the top level:

    map<string, int> memo = {}; 
    cout << countConstruct("abcdef", {"ab", "abc", "cd", "def", "abcd", "ef"}, memo) << endl;`

If C++ recursion can work on passed by value variables which is also making it copy, why not on default arguments? Is there anyway to make it work like the JS code without using global, static variable or reference parameter which is the goal of the question asked? — hbkvikas, Apr 05 '21 at 13:25
See this question for why C++ can't have default arguments passed by reference https://stackoverflow.com/questions/1059630/default-value-to-a-parameter-while-passing-by-reference-in-c — GandhiGandhi, Apr 05 '21 at 13:59
But the bigger reason, is that C++ is not JavaScript. Memory management is the programmers responsibility in C++. — GandhiGandhi, Apr 05 '21 at 14:01

C++: How passed variable in recursive function call behaves? Conditions to correctly modify it?

1 Answers1