Fibonacci recursion with a stack

Question

I've already asked a question about this, yet I'm still confused. I want to convert a recursive function into a stack based function without recursion. Take, for example, the fibonacci function:

algorithm Fibonacci(x):
  i = 0
  i += Fibonacci(x-1)
  i += Fibonacci(x-2)
  return i

(Yes I know I didn't put a base case and that recursion for fibonacci is really inefficient)

How would this be implemented using an explicit stack? For example, if I have the stack as a while loop, I have to jump out of the loop in order to evaluate the first recursion, and I have no way of returning to the line after the first recursion and continue on with the second recursion.

Answer 1

in pseudo python

def fib(x):
  tot = 0
  stack = [x]
  while stack:
     a = stack.pop()
     if a in [0,1]:
        tot += 1
     else:
         stack.push(a - 1)
         stack.push(a - 2)
   return tot

If you do not want the external counter then you will need to push tuples that keep track of the accumulated sum and whether this was a - 1 or a - 2.

It is probably worth your time to explicitly write out the call stack (by hand, on paper) for a run of say fib(3) for your code (though fix your code first so it handles the boundary conditions). Once you do this it should be clear how to do it without a stack.

Edit:

Let us analyze the running of the following Fibonacci algorithm

def fib(x):
    if (x == 0) or (x == 1):
       return 1
    else:
        temp1 = fib(x - 1)
        temp2 = fib(x - 2)
        return temp1 + temp2

(Yes, I know that this isn't even an efficient implementation of an inefficient algorithm, I have declared more temporaries than necessary.)

Now when we use a stack for function calling we need to store two kinds of things on the stack.

1. Where to return the result.
2. Space for local variables.

In our case we have three possible places to return to.

1. Some outside caller
2. Assign to temp1
3. Assign to temp2

we also need space for three local variables x, temp1, and temp2. let us examine fib(3)

when we initially call fib we tell the stack that we want to return to wherever we cam from, x = 3, and temp1 and temp2 are uninitialized.

Next we push onto the stack that we want to assign temp1, x = 2 and temp1 and temp2 are uninitialized. We call again and we have a stack of

(assign temp1, x = 1, -, -)
(assign temp1, x = 2, -, -)
(out         , x = 3, -, -)

we now return 1 and do the second call and get

(assign temp2, x = 0, -, -)
(assign temp1, x = 2, temp1 = 1, -)
(out         , x = 3, -, -)

this now again returns 1

(assign temp1, x = 2, temp1 = 1, temp2 = 1)
(out         , x = 3, -, -)

so this returns 2 and we get

(out         , x = 3, temp1 =2, -)

So we now recurse to

(assign temp2, x = 1, -, -)
(out         , x = 3, temp1 =2, -)

from which we can see our way out.