漫谈递归:从斐波那契开始了解尾递归

对尾递归的大概了解
服务器君一共花费了217.832 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

尾递归(tail recursive),看名字就知道是某种形式的递归。简单的说递归就是函数自己调用自己。那尾递归和递归之间的差别就只能体现在参数上了。

尾递归wiki解释如下:

尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数,如果在递归函数中,递归调用返回的结果总被直接返回,则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言,而且从编译器角度来说,亦容易优化成为普通循环。这是因为从电脑的基本面来说,所有的循环都是利用重复移跳到代码的开头来实现的。如果有尾部归递,就只需要叠套一个堆栈,因为电脑只需要将函数的参数改变再重新调用一次。利用尾部递归最主要的目的是要优化,例如在Scheme语言中,明确规定必须针对尾部递归作优化。可见尾部递归的作用,是非常依赖于具体实现的。

我们还是从简单的斐波那契开始了解尾递归吧。

用普通的递归计算Fibonacci数列:

#include "stdio.h"
#include "math.h"

int factorial(int n);

int main(void)
{
    int i, n, rs;

    printf("请输入斐波那契数n:");
    scanf("%d",&n);

    rs = factorial(n);
    printf("%d \n", rs);

    return 0;
}

// 递归
int factorial(int n)
{
    if(n <= 2)
    {
        return 1;
    }
    else
    {
        return factorial(n-1) + factorial(n-2);
    }
}

程序员运行结果如下:

请输入斐波那契数n:20
6765

Process returned 0 (0x0)   execution time : 3.502 s
Press any key to continue.

在i5的CPU下也要花费 3.502 秒的时间。

下面我们看看如何用尾递归实现斐波那契数。

#include "stdio.h"
#include "math.h"

int factorial(int n);

int main(void)
{
    int i, n, rs;

    printf("请输入斐波那契数n:");
    scanf("%d",&n);

    rs = factorial_tail(n, 1, 1);
    printf("%d ", rs);

    return 0;
}

int factorial_tail(int n,int acc1,int acc2)
{
    if (n < 2)
    {
        return acc1;
    }
    else
    {
        return factorial_tail(n-1,acc2,acc1+acc2);
    }
}

程序员运行结果如下:

请输入斐波那契数n:20
6765
Process returned 0 (0x0)   execution time : 1.460 s
Press any key to continue.

快了一倍有多。当然这是不完全统计,有兴趣的话可以自行计算大规模的值,这里只是介绍尾递归而已。

我们可以打印一下程序的执行过程,函数加入下面的打印语句:

int factorial_tail(int n,int acc1,int acc2)
{
    if (n < 2)
    {
        return acc1;
    }
    else
    {
        printf("factorial_tail(%d, %d, %d) \n",n-1,acc2,acc1+acc2);
        return factorial_tail(n-1,acc2,acc1+acc2);
    }
}

程序运行结果:

请输入斐波那契数n:10
factorial_tail(9, 1, 2)
factorial_tail(8, 2, 3)
factorial_tail(7, 3, 5)
factorial_tail(6, 5, 8)
factorial_tail(5, 8, 13)
factorial_tail(4, 13, 21)
factorial_tail(3, 21, 34)
factorial_tail(2, 34, 55)
factorial_tail(1, 55, 89)
55
Process returned 0 (0x0)   execution time : 1.393 s
Press any key to continue.

从上面的调试就可以很清晰地看出尾递归的计算过程了。acc1就是第n个数,而acc2就是第n与第n+1个数的和,这就是我们前面讲到的“迭代”的精髓,计算结果参与到下一次的计算,从而减少很多重复计算量。

fibonacci(n-1,acc2,acc1+acc2)真是神来之笔,原本朴素的递归产生的栈的层次像二叉树一样,以指数级增长,但是现在栈的层次却像是数组,变成线性增长了,实在是奇妙,总结起来也很简单,原本栈是先扩展开,然后边收拢边计算结果,现在却变成在调用自身的同时通过参数来计算。

小结

尾递归的本质是:将单次计算的结果缓存起来,传递给下次调用,相当于自动累积。

在Java等命令式语言中,尾递归使用非常少见,因为我们可以直接用循环解决。而在函数式语言中,尾递归却是一种神器,要实现循环就靠它了。

很多人可能会有疑问,为什么尾递归也是递归,却不会造成栈溢出呢?因为编译器通常都会对尾递归进行优化。编译器会发现根本没有必要存储栈信息了,因而会在函数尾直接清空相关的栈。

延伸阅读

此文章所在专题列表如下:

  1. 漫谈递归:递归的思想
  2. 漫谈递归:递归需要满足的两个条件
  3. 漫谈递归:字符串回文现象的递归判断
  4. 漫谈递归:二分查找算法的递归实现
  5. 漫谈递归:递归的效率问题
  6. 漫谈递归:递归与循环
  7. 漫谈递归:循环与迭代是一回事吗?
  8. 递归计算过程与迭代计算过程
  9. 漫谈递归:从斐波那契开始了解尾递归
  10. 漫谈递归:尾递归与CPS
  11. 漫谈递归:补充一些Continuation的知识
  12. 漫谈递归:PHP里的尾递归及其优化
  13. 漫谈递归:从汇编看尾递归的优化

本文地址:http://www.nowamagic.net/librarys/veda/detail/2325,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2325

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《致加西亚的信》 阿尔伯特·哈伯德(Hubbard.E.) (作者), 赵立光 (译者), 艾柯 (译者)

《致加西亚的信(经典盒装版)》内容简介:美西战争爆发以后,美国必须立即与古巴起义军首领加西亚取得联系,并获得他的合作。但当时,加西亚身在古巴的深山里——没有人知道他的确切地点,所以没法与他取得联系。这时,有人向总统推荐一个名叫罗文的人,说他有办法找到加西亚,而且也只有他才能找得到。他们找来罗文,交给他一封写给加西亚的信。三周后,罗文徒步走过一个危机四伏的国家,最终把那封信交给了加西亚。 此后,罗文的事迹被传为佳话,“送信”成为了敬业、忠诚、勤奋的象征,罗文便成了每个领导都想找到的人和每个员工都应该学习和效仿的榜样。

更多计算机宝库...