Rewriting a recursive function without using recursion

Question

I'm rewriting some existing code in a setting where recursive calls are not easily implemented nor desired. (And in Fortran 77, if you must know.) I've thought about making a stack from scratch to keep track of the calls needed, but this seems kludgy, and I'd rather not allocate memory to an array in cases where the recursion is not deep. (I'm not confident that Fortran 77 supports dynamic array sizing either.)

Any other suggestions for a general solution on how to take an obviously recursive function and rewrite it non-recursively without wasting space on a stack?

If it doesn't branch you can usually rewrite it into a simple loop. If it branches you usually need a stack — CodesInChaos, Dec 12 '10 at 14:14
@CodeInChaos: a recursive function that does not branch will, by definition, never return... — Victor Nicollet, Dec 12 '10 at 14:18
Guess I misused the word branch. I mean calls itself multiple times, so the graph of calls becomes a tree with branches. And it's only my experience and not always true. — CodesInChaos, Dec 12 '10 at 14:21

score 17 · Accepted Answer · answered Dec 12 '10 at 14:17

17

If your code uses tail recursion (that is, the function returns the result of every recursive call directly without any other processing) then it's possible to rewrite the function imperatively without a stack:

function dosomething(a,b,c,d) 
{
  // manipulate a,b,c,d
  if (condition) 
    return dosomething(a,b,c,d) 
  else
    return something;
}

Into:

function dosomething(a,b,c,d) 
{
  while (true) 
  {
    // manipulate a,b,c,d
    if (condition) continue;
    else return something;
  }
}

Without tail recursion, using a stack (or a similar intermediary storage) is the only solution.

answered Dec 12 '10 at 14:17

Victor Nicollet

24,361
4
58
89

This is similar to what I was thinking, but could not put into words. So in my particular case, I have a data set of elements that will each need to be tested for a relationship to other elements in the set. I could pass in the data structure of all the items, but since each needs further processing, I suppose the stack is inevitable, yes? – Old McStopher Dec 12 '10 at 14:30
Depends. If the code is mostly "for all pairs (a,b) if P(a,b) is true then execute F(a,b)" you can get away with iteratively looping through all the pairs... – Victor Nicollet Dec 12 '10 at 14:39

score 3 · Answer 2 · answered Dec 12 '10 at 16:51

The classic recursive function that can be written as a loop is the Fibonacci function:

 function fib(n)
 {
     // valid for n >= 0
     if (n < 2)
         return n;
     else
         return fib(n-1) + fib(n-2);
 }

But without memoization this takes O(exp^N) operations with O(N) stack space.

It can be rewritten:

 function fib(n)
 {
     if (n < 2)
        return n;
     var a = 0, b = 1;
     while (n > 1)
     {
         var tmp = a;
         a = b;
         b = b + tmp;
         n = n - 1;
     }   
     return b;
 }

But this involves knowledge of how the function works, not sure if it can be generalized to an automatic process.

score 2 · Answer 3 · answered Dec 12 '10 at 14:15

2

Most recursive functions can be easily rewritten as loops, as to wasting space - that depends on the function, since many (but not all) recursive algorithms actually depend on that kind of storage (although, the loop version is usually more efficient in these cases too).

answered Dec 12 '10 at 14:15

Ofir

8,194
2
29
44

Care to show a recursive function not requiring any space on stack? Even for its arguments? – Nikita Rybak Dec 12 '10 at 14:28
2

@Nikita Rybak : an inlined tail-recursive function ;) – Victor Nicollet Dec 12 '10 at 14:37
@Victor Yeah, but that's in rewritten form. And Ofir claims there's a recursive function not requiring stack memory. So, I'm curious. – Nikita Rybak Dec 12 '10 at 15:10
@Jason Are you saying that your recursive function does not "depend on that kind of storage"? – Nikita Rybak Dec 12 '10 at 16:57
1

Contrast a recursive algorithm, from a recursive implementation of that algorithm. The latter always requires stack space when not an example of tail recursion. The former depends on how it is implemented. – Jason S Dec 12 '10 at 17:01

Rewriting a recursive function without using recursion

3 Answers3

Linked