什么是尾递归

尾递归

一、概念

​ 如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

二、实例

以递归的形式计算阶乘：

线性递归:

long Rescuvie( long n) {
    return (n == 1) ? 1 : n * Rescuvie(n - 1);
}

尾递归:

long TailRescuvie( long n, long a) {
    return (n == 1) ? a : TailRescuvie(n - 1, a * n); 
} 
long TailRescuvie( long n) {//封装用的
    return (n == 0) ? 1 : TailRescuvie(n, 1); 
}

当n = 5时
对于传统线性递归, 他的递归过程如下:

Rescuvie(5)

{5 * Rescuvie(4)}

{5 * {4 * Rescuvie(3)}}

{5 * {4 * {3 * Rescuvie(2)}}}

{5 * {4 * {3 * {2 * Rescuvie(1)}}}}

{5 * {4 * {3 * {2 * 1}}}}

{5 * {4 * {3 * 2}}}

{5 * {4 * 6}}

{5 * 24}

120

对于尾递归, 他的递归过程如下:

TailRescuvie(5)                  // 所以在运算上和内存占用上节省了很多,直接传回结果

TailRescuvie(5, 1)                         return 120
                                                 ↑
TailRescuvie(4, 5)                         return 120
                                                 ↑
TailRescuvie(3, 20)                        return 120
                                                 ↑
TailRescuvie(2, 60)                        return 120
                                                 ↑
TailRescuvie(1, 120)                       return 120
                                                 ↑
120                                //当运行到最后时,return a => return 120 ,将120返回上一级

说明：其实尾递归也需要下层往上层返回结果，但在返回的过程中不用再做计算，依次返回结果即可。从上可以看到尾递归把返回结果放到了调用的参数里。这个细小的变化导致，TailRescuvie(n)不必像以前一样，非要等到拿到了TailRescuvie(n-1)的返回值，才能计算它自己的返回结果,它完全就等于TailRescuvie(n-1)的返回值。因此理论上：TailRescuvie(n)在调用tailTailRescuvie(n-1)前，完全就可以先销毁自己放在栈上的东西。

三、优势

​ 与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此每一个函数在调用下一个函数之前，都能做到先把当前自己占用的栈给先释放了，尾递归的调用链上可以做到只有一个函数在使用栈，因此可以无限地调用！

​ 但是，上述的优化是在某些语言编译器的优化支持上实现的，尾递归本身并不能消除函数调用栈过长的问题。在一般递归函数func()中，func(n)是依赖于 func(n-1) 的，func(n) 只有在得到 func(n-1) 的结果之后，才能计算它自己的返回值，因此理论上，在 func(n-1) 返回之前，func(n)，不能结束返回。因此func(n)就必须保留它在栈上的数据，直到func(n-1)先返回，而尾递归的实现则可以在编译器的帮助下，消除这个限制。

四、尾递归的调用栈优化特性

#include <stdio.h>

int tail_func(int n, int res){
     if (n <= 1) return res;
     return tail_func(n - 1, n * res);
}

int main(){
    int dummy[1024*1024]; // 尽可能占用栈。
    tail_func(2048*2048, 1);
    return 1;
}

​ 上面这个程序在开了编译优化和没开编译优化的情况下编出来的结果是不一样的，如果不开启优化，直接 gcc -o tr func_tail.c 编译然后运行的话，程序会爆栈崩溃，但如果开优化的话：gcc -o tr -O2 func_tail.c，上面的程序最后就能正常运行。 这里面的原因就在于，尾递归的写法只是具备了使当前函数在调用下一个函数前把当前占有的栈销毁，但是会不会真的这样做，是要具体看编译器是否最终这样做，如果在语言层面上，没有规定要优化这种尾调用，那编译器就可以有自己的选择来做不同的实现，在这种情况下，尾递归就不一定能解决一般递归的问题。

参考链接:

什么是尾递归,尾递归的优势以及语言支持情况说明

说说尾递归