浅谈从斐波那契数列开始了解尾部递归

 

递归分为：不动点组合子，尾部递归还有递归数据，目前 我只研究到尾部递归 

 

再了解递归前我们先了解一下什么是斐波那契数列?

所谓Fibonacci数列是指这样一种数列，它的前两项均为1，从第三项开始各项均为前两项之和。用数学公式表示出来就是：

           1                            (n=1,2)

fib(n)=

 

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

 

例如：

有这样一组数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

特别指出：第0项是0，第1项是第一个1。

这个数列从第二项开始，每一项都等于前两项之和。

所以它的公式应该是：a1=1,a2=2,an=a(n-1)+a(n-2)(n>=3)

 

其它信息各位可以百度看一下

http://baike.baidu.com/link?url=F-D2_4R1w5gCz5uFcR2drVZAMFQm2g22HYyXkj01u-5DFRrh9owiOdtr982VyreQ

 

 

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

维基百简直是如下解释的：

尾部递归[编辑]

主条目：尾部递归

尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。 因此，在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘，但是使用尾部递归：^[4]

 

尾递归解释如下：

尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数，如果在递归函数中，递归调用返回的结果总被直接返回，则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言，而且从编译器角度来说，亦容易优化成为普通循环。这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。如果有尾部归递，就只需要叠套一个堆栈，因为电脑只需要将函数的参数改变再重新调用一次。利用尾部递归最主要的目的是要优化，例如在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.

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

 

 

 

#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)将原本朴素的递归产生的栈的层次像二叉树一样，以指数级增长，但是现在栈的层次却像是数组，变成线性增长了，实在是奇妙，总结起来也很简单，原本栈是先扩展开，然后边收拢边计算结果，现在却变成在调用自身的同时通过参数来计算。