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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

请不要在回答技术问题时复制粘贴 AI 生成的内容

这是一个创建于 1516 天前的主题，其中的信息可能已经有所发展或是发生改变。

int fib(int n) {

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

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

fib

递归

int

return

9 条回复 2021-10-07 12:27:34 +08:00

v2mm

2021-10-06 22:38:34 +08:00

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

2021-10-06 22:42:19 +08:00

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

AoEiuV020

2021-10-06 22:59:13 +08:00 via Android

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

metitation

2021-10-06 23:07:20 +08:00

是我搞错了，标准的是 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

2021-10-06 23:23:16 +08:00

一楼写的就挺好的。

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

akira

2021-10-06 23:56:44 +08:00

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

vance123

2021-10-07 02:26:56 +08:00

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

jinliming2

2021-10-07 12:10:51 +08:00

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

lonewolfakela

2021-10-07 12:27:34 +08:00

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 出来……