算法与数据结构 | 解析递归与尾递归_尾递归原理

一.什么是尾递归

在之前的的第一篇文章中深入的探讨了什么递归，并在文末引出了一种新的递归方式：尾递归。

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

定义是很官方的，接下来我会用最通俗的语言说明什么尾递归。简单来说，尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数。

二.尾递归的原理

当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

三.递归与尾递归的区别

我们先通过大家熟知的阶乘函数来举例：

int fact(int n) {
    if (n < 0)
        return 0;
    else if(n == 0 || n == 1)
        return 1;
    else
        return n * fact(n - 1);
}
1
2
3
4
5
6
7
8

int fact(int n, int result)
{
    if (n < 0)
        return 0;
    else if (n == 0)
        return 1;
    else if (n == 1)
        return result;
    else
        return fact(n - 1, n * result);
}

1
2
3
4
5
6
7
8
9
10
11
12

显然，代码一是一个普通的递归，代码二则是一个尾递归。我们观察两者的不同就会发现:
1.尾递归多加了一个参数result作为结果进行返回，我们调用时初始传入result=1.
2.尾递归在递归调用时并没有再出现n，而是直接调用了本函数，这也就是定义中说的返回值不属于某一表达式的一部分，而是仅仅只调用本函数。

四.尾递归的特点

尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.

我们再来看一个更加清楚的例子，这个例子会完美的阐释尾递归的威力：

//普通的线性递归：
long Rescuvie(long n) {
    return (n == 1) ? 1 : n * Rescuvie(n - 1);
}
1
2
3
4

//尾递归
long TailRescuvie(long n, long result) {
  return (n == 1) ? result : TailRescuvie(n - 1, result * n);
}
long TailRescuvie(long n) {//封装用的
    return (n == 0) ? 1 : TailRescuvie(n, 1); 
}
1
2
3
4
5
6
7

这里我们可以看到在尾递归中写了两个函数，这里用到了函数的重载，即我们通过调用第二个函数从而再递归的调用第一个函数。

接下类我们一步步的执行普通的线性递归和尾递归，观察两者的不同。

当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)
TailRescuvie(4, 5)
TailRescuvie(3, 20)
TailRescuvie(2, 60)
TailRescuvie(1, 120)
120

这里我们便很容易看出, 普通的线性递归比尾递归更加消耗资源, 在实现上说, 每次重复的过程
调用都使得调用链条不断加长. 系统不得不使用栈进行数据保存和恢复.而尾递归就不存在这样的问题, 因为他的状态完全由n和result保存，且一直充当参数，所以栈每次只用保存后一个函数即可，因此我们可以形象的说尾递归就是不压栈的递归。

五.尾递归的作用及其重要性

显然尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。比如sum(n) = f(n) = f(n-1) + value(n) ;会保存n个函数调用堆栈，而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留一个函数堆栈即可，之前的可优化删去。

而尾递归的用途一般会在erlang这个语言中发挥的淋漓尽致，因为erlang是一种函数式编程语言，erlang中没有循环，只能通过递归和列表解析来实现循环的功能。但众所周知递归典型的代码简洁但效率极低的，所以通过尾递归来对递归进行优化就显然锦上添花了。

六.一个用例

在前一篇文章中我们用python实现了快速排序，那么我们最后在用C语言和尾递归来实现一下快速排序

void quickSort(SqList * list , int low ,int high)
{
	 int pivot;
	 while(low<high)
    {
        pivot=Partition(list,low,high);
 
        quickSort(list, low,pivot - 1);
 
        //quickSort(list,low,pivot-1); /*原递归调用需要两行代码*/
 
        //quickSort(list,pivot+1,high);
 
        low = pivot+1; /*尾递归*/
 
    }
 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18