Fibonacci recursion with stack

Question

I already asked a question about this, but I'm still confused. I want to convert a recursive function to 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 that I did not set the base register and that recursion for fibonacci is really inefficient)

How will this be implemented using an explicit stack ? For example, if I have a stack as a while loop, I have to jump out of the loop to evaluate the first recursion, and I have no way to go back to the line after the first recursion and continue 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

, , a - 1 a - 2.

, , (, ) (3) ( , ). , , .

Edit:

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

(, , , , .)

, , .

• .
• .

.

• temp1
• temp2

x, temp1 temp2. fib (3)

fib, , , , x = 3 temp1 temp2 .

, temp1, x = 2 temp1 temp2 . ,

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

1

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

1

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

2

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

,

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

.

Answer 2

, , , , . , , .

. #. 0 0 - , , " ". . .

, . , enum

enum JumpAddress
{
    beforeTheFirstRecursiveInvocation,
    betweenRecursiveInvocations,
    afterTheSecondRecursiveInvocation,
    outsideFibFunction
}

.

, , :

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;
    }
}

# - . , , , :

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

, , .

, - beforeTheFirstRecursiveInvocation.

, lastresult, pointOfExecution , , .

.

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 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;
}

Answer 3

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

.

" ", , , , , , .

Answer 4

// 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];
}

   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;
}

, 2 .