Fibonacci recursion with a stack

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 wi开发者_JAVA技巧thout 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.

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.

algorithm Fibonacci(x):
  stack = [1,1]
  while stack.length < x
    push to the stack the sum of two topmost stack elements
  return stack.last

You can preserve stack between calls as some kind of cache.

This stack is not a "true stack" since you can do more than only pushing, popping and checking its emptiness, but I believe this is what you are planning to do.

Your question inspired me to write a piece of code, that initially scared me, but I'm not really sure what to think about it now, so here it is for Your amusement. Maybe it can help a bit, with understanding things.

It's a blatant simulation of an execution of a recursive Fibonacci function implementation. The language is C#. For an argument 0 the function returns 0 - according to the definition of the Fibonacci sequence given by Ronald Graham, Donald Knuth, and Oren Patashnik in "Concrete Mathematics". It's defined this way also in Wikipedia. Checks for negative arguments are omitted.

Normally a return address is stored on the stack and execution just jumps to the right address. To simulate this I used an enum

enum JumpAddress
{
    beforeTheFirstRecursiveInvocation,
    betweenRecursiveInvocations,
    afterTheSecondRecursiveInvocation,
    outsideFibFunction
}

and a little state machine.

The Frame stored on the stack is defined like this:

class Frame
{
    public int argument;
    public int localVariable;
    public JumpAddress returnAddress;
    public Frame(int argument, JumpAddress returnAddress)
    {
        this.argument = argument;
        this.localVariable = 0;
        this.returnAddress = returnAddress;
    }
}

It's a C# class - a reference type. The stack holds references to the objects placed on the heap, so when I'm doing this:

Frame top = stack.Peek();
top.localVariable = lastresult;

I'm modifying the object still referenced by the reference at the top of a stack, not a copy.

I model invocation of a function, by pushing a frame on the stack and setting the execution address in my state machine to the beginning - beforeTheFirstRecursiveInvocation.

To return form the function I set the lastresult variable, pointOfExecution variable to the return address stored in the top frame and pop the frame from the stack.

Here is the code.

public static int fib(int n)
{
    Stack<Frame> stack = new Stack<Frame>(n);
    //Constructor uses the parameter to reserve space.
    int lastresult = 0; 
    //variable holding the result of the last "recursive" invocation            
    stack.Push(new Frame(n, JumpAddress.outsideFibFunction));
    JumpAddress pointOfExecution = JumpAddress.beforeTheFirstRecursiveInvocation;
    // that's how I model function invocation. I push a frame on the stack and set
    // pointOfExecution. Above the frame stores the argument n and a return address
    // - outsideFibFunction

    while(pointOfExecution != JumpAddress.outsideFibFunction)
    {
        Frame top = stack.Peek();
        switch(pointOfExecution)
        {
            case JumpAddress.beforeTheFirstRecursiveInvocation:
                if(top.argument <= 1)
                {
                    lastresult = top.argument;
                    pointOfExecution = top.returnAddress;
                    stack.Pop();
                }
                else
                {
                    stack.Push(new Frame(top.argument - 1, JumpAddress.betweenRecursiveInvocations));
                    pointOfExecution = JumpAddress.beforeTheFirstRecursiveInvocation;
                }
                break;
            case JumpAddress.betweenRecursiveInvocations:
                top.localVariable = lastresult;
                stack.Push(new Frame(top.argument - 2, JumpAddress.afterTheSecondRecursiveInvocation));
                pointOfExecution = JumpAddress.beforeTheFirstRecursiveInvocation;
                break;
            case JumpAddress.afterTheSecondRecursiveInvocation:
                lastresult += top.localVariable;
                pointOfExecution = top.returnAddress;
                stack.Pop();
                break;
            default:
                System.Diagnostics.Debug.Assert(false,"This point should never be reached");
                break;
        }
    }
    return lastresult;
}

// 0<x<100
int fib[100];
fib[1]=1;
fib[2]=1;
if(x<=2)
cout<<1;
else{
for(i=3;i<=x;i++)
   fib[i]=fib[i-1]+fib[i-2];
cout<<fib[x];
}

OR without using a vector

   int x,y,z;
   x=1;y=1;z=1;
   if(x<=2)
    cout<<1;
   else{
   for(i=3;i<=x;i++){
      z=x+y;
      x=y;
      y=z;
}
cout<<z;
}

The last method works because you only need the previous 2 fibonacci numbers for creating the current one.