Stack overflow due to deep recursion

Question

I have an assignment to solve the coin change problem which goes like this: i have 5 types of coins {1,5,10,25,50}, We want to make changes with these coins for a given amount of money, in how many ways can i form up 11 cents for example, or n cents in general ? my program should be able to handle up to 7489 cents as an input.

i used recursion and dynamic programming to solve the problem but i get a stack overflow error during runtime at (input >= 3980)

How do i solve this error ?

#include <iostream>
using namespace std;
typedef long long ll;
int Cents[5] = { 1,5,10,25,50 }, in, mem[5][7495];

ll CC(int i, int val) { // this is where the recursion happens
    if (val == 0)   return 1;
    if (i == 5) return 0;
    if (mem[i][val] != -1) return mem[i][val];
    long long op1 = CC(i + 1, val);
    long long op2 = Cents[i] <= val ? CC(i, val - Cents[i]) : 0;
    return  mem[i][val] = (op1+op2);
}

int main() { // here i pass an input and fill the mem 2d array with -1's
    scanf_s("%d", &in);
    memset(mem, -1, sizeof mem);
    printf("%lld\n", CC(0, in));
    system("pause");
    return 0;
}

if the input is 5 for example, then the output should be 2 ways (1),(5) if 11 , then 4 (1*11),(1*6,5*1),(10*1,1*1),(1*1,5*2) and so on.

Answer 1

You have a stack overflow because your recursion depth is limited by only the size of your array and the number of pennies. And your stack state is reasonable in size.

One solution is to go with an explicit stack.

enum coins {
  penny, nickle, dime, quarter, half,
  coin_count
};
enum {
  max_cash = 7495
};
struct coin_problem {
  coins lowest_coin = penny;
  int money = 0;
};
struct coin_cache {
  unsigned long long solution[coin_count][max_cash+1];
  coin_cache(){
    for(auto& row:solution)
      for(auto& val:row)
        val=-1;
  }
  unsigned long long& set(coin_problem p){
    return solution[p.lowest_coin][p.money];
  }
  unsigned long long get(coin_problem p)const{
    if(p.lowest_coin==coin_count) return 0;
    if(p.money==0) return 0;
    return solution[p.lowest_coin][p.money];
  }
};
unsigned long long count_solutions( std::vector<coin_problem>& vec, coin_cache& cache){
  unsinged long lon retval = 0;
  while(!vec.empty()){
    auto cur = vec.back();
    retval = cache.get[cur];
    if (retval != -1) {
      vec.pop_back();
      continue;
    }
    ++cur.lowest_coin;
    auto op1 = cache.get[cur];
    if (op1 == -1) vec.push_back(cur);
    --cur.lowest_coin;
    unsigned long long op2 = -1;
    if(Cents[cur.lowest_coin] <= cur.money){
      cur.money -= Cents[cur.lowest_coin];
      op2 = cache.get[cur];
      if (op2==-1) vec.push_back(cur);
      cur.money += Cents[cur.lowest_coin];
    } else {
      op2 = 0;
    }
    if (op1 != -1 && op2 != -1){
      retval = cache.set(cur) = op1+op2;
      vec.pop_back();
    }
  }
  return retval;
}
unsigned long long count_solutions( coin_problem p ){
  auto pcache = std::make_unique<coin_cache>();
  std::vector<coin_problem> todo = {p};
  return count_solutions( todo, *pcache );
}

I tore your recursive solution up and gave it a manual stack.

For each entry in the stack of problems, we first see if there is a solution waiting in the cache. If so, we calculate it, and store it in the cache, and pop the problem. If the stack of problems is empty, we return it.

If not, we push sub problems to solve first onto the top if the stack, leaving our current problem to be solved later, and loop until the stack is empty.

As our manual stack exists on the free store (aka the heap) we are unlikely to experience a stack overflow on a desktop system.

This isn't perfectly efficient, as we can have more than one entry on the stack for each problem. But that should be at most a constand factor, and can be likely fixed by reordering the "recursion" to do the "deepest" call first. Or making the stack of problems a set of problems ordered by depth.

Another approach is to just solve every entry in the table, deepest first.