5
假设你使用的程序语言不支持递归程序，如果要求用栈来模拟下面这个斐波那契求第 n 项...
source link: https://www.v2ex.com/t/806141
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
假设你使用的程序语言不支持递归程序，如果要求用栈来模拟下面这个斐波那契求第 n 项的程序，应该如何转换成等价的基于栈的非递归实现？
metitation · 1 天前 · 928 次点击int fib(int n) {
if(n == 1 || n == 2) { return n; }
return fib(n-1) + fib(n-2)
9 条回复 • 2021-10-07 12:27:34 +08:00
v2mm 1 天前
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);
}
}
sum = 0;
while (!stack.empty())
{
i = stack.pop()
if(i == 1 || i == 2)
sum += i;
else
{
stack.push(i-1);
stack.push(i-2);
}
}
AoEiuV020 1 天前 via Android
啊这，是来出考题的吗，斐波那契搞递归本来就是底效的了，强行模拟递归就更难看了，
而且模拟递归是固定套路和具体题目没啥关系吧，
另外斐波那契前两项是 1 不是 n，1 楼都被楼主带偏了，
而且模拟递归是固定套路和具体题目没啥关系吧，
另外斐波那契前两项是 1 不是 n，1 楼都被楼主带偏了，
metitation 1 天前
是我搞错了，标准的是 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*）
但是一般说是 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 1 天前
一楼写的就挺好的。
调用栈可以看成树，求值本质上就是多叉树遍历，比如从 fib(5) 一路遍历下来 fib(0) 和 fib(1) 就可以在纸上画成一颗树，所以抄一个迭代版 DFS 改一改其实就出来一楼的结果了。
调用栈可以看成树，求值本质上就是多叉树遍历，比如从 fib(5) 一路遍历下来 fib(0) 和 fib(1) 就可以在纸上画成一颗树，所以抄一个迭代版 DFS 改一改其实就出来一楼的结果了。
lonewolfakela 20 小时 22 分钟前
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 出来……
{
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 出来……
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK