CODEWITHSUNDEEP
recursionstack
fieryrage
fieryrage

Reputation: 69

Replacing recursion (with return values) with explicit stack

I was just wondering whether if it was possible to replace recursion with an explicit stack when you need the return value(s) and are comparing them to find the best solution (like dynamic programming)?

So something like (it doesn't do anything, just an example):

int resursiveFunction (int state) { 

   if (known[state]) return cache[state];
   if (state == MAX_STATE) return 0;

   int max = 0;

   for (int i = 0 ; i < 5; i++) {
      int points = curPoints (state) + recursiveFunction (state+i);
      if (points > max) max = points; 
   }

   known[state] = true;
   cache[state] = max;
   return max;

}

Upvotes: 2

Views: 2401

Answers (1)

user166390
user166390

Reputation:

Yes. It's possible.

Simply push and pop as appropriate. Recursion simply creates an 'implicit stack'. You can unwind TCO'able recursive functions as well.

You may find Stacks and Recursion Elimination (it's for a course) useful. It covers elimination (left-recursive) as well as emulation (stack).

Upvotes: 3

Related Questions