qq_43412960
qq_43412960
采纳率79.1%
2019-10-26 18:18

这是一个关于函数递归的相关问题

5
已采纳

图片说明

这个例子中,rentun 里出现的递归函数,这是传说中的尾递归吗?
感觉这种递归不会占太多内存。因为执行return 就开始释放内存了。
return +递归函数,这种的

应该是1级函数释放掉,执行2级return 的函数,然后2级return 的函数,释放掉,执行3级的,其实用的差不多都是相同位置的内存,我的理解没错吧

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • caozhy 回答这么多问题就耍赖把我的积分一笔勾销了 2年前

    不是尾递归,因为f被递归调用2次,无论先算前一个表达式或者后一个表达式,都需要一个变量来缓存。因此不能不需要堆栈。

    long f1(int m, int i, int a, int b);
    
    long f(int m)
    {
    if (m < 3) return 1;
    return f1(m, 3, 1, 1);
    }
    
    long f1(int m, int i, int a, int b)
    {
    if (i > m) return b;
    b = a + b;
    a = b - a;
    return f1(m, i + 1,  a, b);
    }
    

    这是尾递归(我是指f1函数,作为最初的f不是递归),等价的循环:

    long f(int m)
    {
    int a = 1;
    int b = 1;
    for (int i = 3; i <= m; i++)
    {
    b = a + b;
    a = b - a;
    }
    return b;
    }
    

    但是要注意,c语言并不能把尾递归转换成循环,只是在逻辑上有这种等价关系。因此即便按照我给的代码,仍然还是需要堆栈存储,还是有递归深度的限制。

    点赞 1 评论 复制链接分享

为你推荐