首页 > 代码库 > 从斐波那契开始了解尾递归

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

2024-07-22 10:52:13   223人阅读

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

尾递归wiki解释如下：豪享博娱乐城

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

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

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

01#include "stdio.h"
02#include "math.h"
03 
04int factorial(int n);
05 
06int main(void)
07{
08    int i, n, rs;
09 
10    printf("请输入斐波那契数n：");
11    scanf("%d",&n);
12 
13    rs = factorial(n);
14    printf("%d \n", rs);
15 
16    return 0;
17}
18 
19// 递归
20int factorial(int n)
21{
22    if(n <= 2)
23    {
24        return 1;
25    }
26    else
27    {
28        return factorial(n-1) + factorial(n-2);
29    }
30}

程序员运行结果如下：

1请输入斐波那契数n：20
26765
3 
4Process returned 0 (0x0)   execution time : 3.502 s
5Press any key to continue.

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

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

01#include "stdio.h"
02#include "math.h"
03 
04int factorial(int n);
05 
06int main(void)
07{
08    int i, n, rs;
09 
10    printf("请输入斐波那契数n：");
11    scanf("%d",&n);
12 
13    rs = factorial_tail(n, 1, 1);
14    printf("%d ", rs);
15 
16    return 0;
17}
18 
19int factorial_tail(int n,int acc1,int acc2)
20{
21    if (n < 2)
22    {
23        return acc1;
24    }
25    else
26    {
27        return factorial_tail(n-1,acc2,acc1+acc2);
28    }
29}

程序员运行结果如下：

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

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

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

01int factorial_tail(int n,int acc1,int acc2)
02{
03    if (n < 2)
04    {
05        return acc1;
06    }
07    else
08    {
09        printf("factorial_tail(%d, %d, %d) \n",n-1,acc2,acc1+acc2);
10        return factorial_tail(n-1,acc2,acc1+acc2);
11    }
12}

程序运行结果：

01请输入斐波那契数n：10
02factorial_tail(9, 1, 2)
03factorial_tail(8, 2, 3)
04factorial_tail(7, 3, 5)
05factorial_tail(6, 5, 8)
06factorial_tail(5, 8, 13)
07factorial_tail(4, 13, 21)
08factorial_tail(3, 21, 34)
09factorial_tail(2, 34, 55)
10factorial_tail(1, 55, 89)
1155
12Process returned 0 (0x0)   execution time : 1.393 s
13Press any key to continue.

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

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

小结

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

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

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

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


联系
我们