假设你使用的程序语言不支持递归程序，如果要求用栈来模拟下面这个斐波那契求第 n 项的程序，应该如何转换成等价的基于栈的非递归实现？

[metitation]

int fib(int n) {

if(n == 1 || n == 2) { return n; }

return fib(n-1) + fib(n-2)

[v2mm]

stack.push(n);
sum = 0;
while (!stack.empty())
{
i = stack.pop()
if(i == 1 || i == 2)
sum += i;
else
{
stack.push(i-1);
stack.push(i-2);
}
}

[metitation]

@v2mm if(i == 1 || i == 2)
sum += 1;

[AoEiuV020]

啊这，是来出考题的吗，斐波那契搞递归本来就是底效的了，强行模拟递归就更难看了，
而且模拟递归是固定套路和具体题目没啥关系吧，
另外斐波那契前两项是 1 不是 n，1 楼都被楼主带偏了，

[metitation]

是我搞错了，标准的是 0 、1 、1 、2 、3 、5 、8 、13 、21 、34 、……
但是一般说是 1 、1 、2 、3 、5 、8 、13 、21 、34 、……
F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（ n ≥ 2，n ∈ N*）

[namelosw]

一楼写的就挺好的。

调用栈可以看成树，求值本质上就是多叉树遍历，比如从 fib(5) 一路遍历下来 fib(0) 和 fib(1) 就可以在纸上画成一颗树，所以抄一个迭代版 DFS 改一改其实就出来一楼的结果了。

[akira]

递归的时候做了啥事情，保留现场 ，压入参数，执行一遍代码，恢复现场 ，重新模拟一遍就是好了啦

[vance123]

如果是```fib(n - 1) + fib(n - 2) * 2```呢？

[jinliming2]

斐波那契数列本身就不需要递归、栈啊，只需要两个变量保存前两项的值就行啊？

[lonewolfakela]

struct fib_state
{
void* ret_addr;
int n;
int n_minus_1;
int n_minus_2;
int ret_val;
};

std::stack<fib_state> stack;

void* call(void* func_addr, int n, void* ret_addr)
{
stack.push(fib_state{ ret_addr, n });
return func_addr;
}

void* ret(int ret_val)
{
void* p = stack.top().ret_addr;
stack.pop();
stack.top().ret_val = ret_val;
return p;
}

int fib(int n)
{
stack.push(fib_state{});
goto* call(&& fib_func, n, && ret);
ret:
return stack.top().ret_val;
fib_func:
if (stack.top().n <= 2)
{
goto* ret(1);
}
{
goto* call(&& fib_func, stack.top().n - 1, && lbl_1);
lbl_1:
stack.top().n_minus_1 = stack.top().ret_val;
}
{
goto* call(&& fib_func, stack.top().n - 2, && lbl_2);
lbl_2:
stack.top().n_minus_2 = stack.top().ret_val;
}
goto* ret(stack.top().n_minus_1 + stack.top().n_minus_2);
}

简单、粗暴、有效、好使。
再复杂的递归函数都能 goto 出来……