Replacing recursion (with return values) with explicit stack

Question

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;

}

score 3 · Accepted Answer · 2010-10-23 22:56:18Z

3

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).

edited Oct 23, 2010 at 22:56

answered Oct 23, 2010 at 22:49

user166390

Sign up to request clarification or add additional context in comments.

1 Comment

fieryrage Over a year ago

Thanks! This is what I needed. "Returning" was what I was confused about.

Collectives™ on Stack Overflow

Replacing recursion (with return values) with explicit stack

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related