尾递归优化

发表于 | 分类于 |

1.什么是尾递归？

       在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置为尾位置。若这个函数在尾位置调用本身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归，是递归的一种特殊情形。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。

       尾调用的重要性在于它可以不在调用栈上面添加一个新的堆栈帧——而是更新它，如同迭代一般。尾递归因而具有两个特征：

  • 调用自身函数(Self-called)；
  • 计算仅占用常量栈空间(Stack Space)。

       而形式上只要是最后一个return语句返回的是一个完整函数，它就是尾递归。

       由于当前函数帧上包含局部变量等等大部分的东西都不需要了，当前的函数帧经过适当的更动以后可以直接当作被尾调用的函数的帧使用，然后程序即可以跳到被尾调用的函数。产生这种函数帧更动代码与 “jump”（而不是一般常规函数调用的代码）的过程称作尾调用消除(Tail Call Elimination)或尾调用优化(Tail Call Optimization, TCO)。尾调用优化让位于尾位置的函数调用跟 goto 语句性能一样高，也因此使得高效的结构编程成为现实。

       一般来说，尾调用消除是可选的。然而，在函数编程语言中，语言标准通常会要求虚拟机实现尾调用消除，这让程序员可以用递归替换循环而不丧失性能。

2. 以Java举例说明尾递归的优化功能

       以Java为例，主要区分普通递归和尾递归对栈空间的使用（Java编译器不支持尾递归优化，不会进行栈的复用，本文只是以Java语言写的递归和尾递归举个例子）：

       普通递归：

1
2
3
4
5
6
int factorial(int n){
     if(n == 1){
         return 1;
     }
     return  n*factorial(n - 1);
 }

       以调用factorial(5)为例，相应的栈空间变化如下：

1
2
3
4
5
6
7
8
9
10
factorial(5)
5*factorial(4)
5*(4*factorial(3))
5*(4*(3*factorial(2))
5*(4*(3*(2*factorial(1)))
5*(4*(3*(2*1)))
5*(4*(3*2))
5*(4*6)
5*24
120

       可观察，堆栈从左到右，增加到一个峰值后再计算从右到左缩小，这往往是我们不希望的，所以在C语言等语言中设计for, while, goto等特殊结构语句，使用迭代、尾递归，对普通递归进行优化，减少可能对内存的极端消耗。修改以上代码，可以成为尾递归：

1
2
3
4
5
6
7
int factorial(int n,int result){
  if(n == 1){
      return result;
  }else{
      return factorial(n - 1,n*result);
   }
}

       同样以factorial(5)为例，相应的栈空间变化如下：

1
2
3
4
5
6
factorial(5,1)
factorial(4,5 * 1)
factorial(3,4 * 5 * 1)
factorial(2,3 * 4 * 5 * 1)
factorial(1,2 * 3 * 4 * 5 * 1)
120

       尾递归对内存的消耗是线性的，每次递归都是调用factorial(x,y)函数自身,复用一个栈。

       而普通递归每次return的是一个表达式n*factorial(n - 1)，需要进行计算并占用一个栈用来存储值，如果n过大会出现堆栈溢出。

       或者使用迭代进行优化(n的阶乘，此处可令n=5)：

1
2
3
4
int result = 1;
 for(int i=1;i<=n;i++){
      result = result*i;
 }

       理论上，所有的递归函数都可以写成迭代的方式，但迭代的逻辑不如递归清晰。事实上，尾递归和迭代的效果是一样的，所以，把迭代看成是一种特殊的尾递归函数也是可以的。