V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
metitation
V2EX  ›  程序员

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

  •  
  •   metitation · 2021-10-06 22:22:55 +08:00 · 1814 次点击
    这是一个创建于 904 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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
    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
        2
    metitation  
    OP
       2021-10-06 22:42:19 +08:00
    @v2mm if(i == 1 || i == 2)
    sum += 1;
    AoEiuV020
        3
    AoEiuV020  
       2021-10-06 22:59:13 +08:00 via Android
    啊这,是来出考题的吗,斐波那契搞递归本来就是底效的了,强行模拟递归就更难看了,
    而且模拟递归是固定套路和具体题目没啥关系吧,
    另外斐波那契前两项是 1 不是 n,1 楼都被楼主带偏了,
    metitation
        4
    metitation  
    OP
       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
        5
    namelosw  
       2021-10-06 23:23:16 +08:00
    一楼写的就挺好的。

    调用栈可以看成树,求值本质上就是多叉树遍历,比如从 fib(5) 一路遍历下来 fib(0) 和 fib(1) 就可以在纸上画成一颗树,所以抄一个迭代版 DFS 改一改其实就出来一楼的结果了。
    akira
        6
    akira  
       2021-10-06 23:56:44 +08:00
    递归的时候做了啥事情,保留现场 ,压入参数,执行一遍代码,恢复现场 ,重新模拟一遍就是好了啦
    vance123
        7
    vance123  
       2021-10-07 02:26:56 +08:00
    如果是```fib(n - 1) + fib(n - 2) * 2```呢?
    jinliming2
        8
    jinliming2  
       2021-10-07 12:10:51 +08:00
    斐波那契数列本身就不需要递归、栈啊,只需要两个变量保存前两项的值就行啊?
    lonewolfakela
        9
    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 出来……
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1502 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:55 · PVG 07:55 · LAX 16:55 · JFK 19:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.