递归、尾递归和函数式编程

时间:2021-12-07 03:32:05

最近看到好多人用手机拍递归照,于是我跟着俗气了一把。这张照片不仅满足我的自拍欲望, 也让我对递归充满了敬意!如果用语言来描述拍照时发生的情景的话,那就是:

  • 现实中的我,在拍照片
  • 照片中的我,在拍照
  • 照片中的我拍的照片中我,在拍照
  • 。。。
  • 第N重世界中的我,还在拍

递归、尾递归和函数式编程
很不幸,无论拍照技术再高超、设备再先进也无法达到无限递归。对此知乎上有专门的讨论。虽说如此,但这并不使我感到沮丧, 对于程序员来说无法停止反而是个灾难。让我觉得有趣的是,假如照片中的我,是个另一唯度的我自己,那么我该如何跟跟任何一个维度中我沟通呢?
假使他们真的存在,那么第一件事就是和他们每一个人打个招呼。这件事情真是非常的简单,我不需要对着他们每个人说一遍,只要和照片中的那个我亲切的打招呼热烈的拥抱,最后叮嘱他做我做过事情,这样每个人都将得到一个招呼和拥抱。
这就是递归的乐趣吧! 废话少说,我们今天要讲的当然不是N重世界,而是和递归有关的编程知识。 一般递归的问题:Fibonacci数列求值可谓递归经典,对于Fibonacci数列的定义用语言来描述就是,第N项是第N-1与第N-2项之和, 第0项和第1项分别是0,1。 数学表示就是F(n) =F(n-1)+F(n-2); F(0) =0; F(1)=1; n>=0 。
用函数递归代码来描述更是直接而又暴力, JavaScript的代码如下:
<span style="font-family:SimSun">function fibonacciRecursivily(n){
if(n==0){
return 0;
}
if(n==1){
return 1;
}
return fibonacciRecursivily(n-1)+fibonacciRecursivily(n-2);
};</span>


函数的递归调用是通过栈来实现的,每一次函数调用都会把当前函数的状态,如变量,返回地址保存在栈中一直到函数返回才能出栈。因为程序运行时,栈的大小一般很有限(在chrome中运行下面的代码可以计算出chrome给每个线程的栈大小),因此如果递归调用的层次如果过多,将会使栈区溢出。
<span style="font-family:SimSun">var n=0;
setTimeout(function(){console.log((n*2/1024)+"KB")}, 1000);
a();
function a(){
n++;
a();
}
</span>
当函数递归调用的栈深度超多栈的最大限度时就会溢出,例如:上面的a(); 很快就会抛出RangeError: Maximum call stack size exceeded
然而fibonacciRecursive(100)并不会抛出栈溢出的错误,因为它的递归深度还不足以占满栈区,但却使程序陷入大量的计算。仔细分析调用过程发现,fibonacciRecursivily(100)的最大栈深度是100,也就是说fibonacciRecursivily算法的空间复杂度是O(n)。 然而它的时间复杂度却是惊人的O(1.618 ^ n)。解决递归时间的问题:
因此有人说Fibonacci是个使用递归的反例,其实不然,问题不能简单的归结递归过程本身的低效,递归过程作为一个问题的语法描述显示出了它的直观和简单。Fibonacci递归实现真正的问题不是过多的栈(空间问题)的使用,而是子问题的重复计算(时间复杂度)。这一点也不足以证明递归是低效,我们只用改变一下算法,避免子问题的重复计算。这类问题通常是动态规划的拿手好戏,于是有了各种利用空间来换取时间的算法,例如用一个数组,来保存数列的值,这样时间和空间的复杂度是O(n)。 使用动态规划的递归调用,把每一次的计算结果保存起来,下一次再次调用时如果有已经计算过就直接取回,而不用重复计算,但在代码上看起来和fibonacciRecursivily却是相似:
<span style="font-family:SimSun">function fibonacciDynamically(n){
var fibonacci =new Array(n+1);
return calculate(n);
}
function calculate(n){
if(n==0)
return fibonacci[n] = 0;
if(n==1)
return fibonacci[n] = 1;
if(fibonacci[n] != undefined)
return fibonacci[n];
else{
return fibonacci[n]=calculate(n-1)+ calculate(n-2);
}
}</span>
虽然在时间得到很大的提高,但是递归的本质并没有什么变化,仍然需要用栈来保存递归调用, 因此在空间上相比fibonacciRecursivily反而额外增加了一个数组,空间复杂度反而有所增加。 这显然不能让人满意,因为我们可以很容易的写出一个更高效的非递归算法:
<span style="font-family:SimSun">function fibonacciIteratively(n){
var a = 0, b = 1;
if(n==0)
return a;
if(n == 1)
return b;
for(var i = 1; i< n;i++){
b = a + b;
a = b - a;
}
return b;
}</span>
递归仍然占每次调用的栈空间:我们不想讨论此问题的非递归方式,然而它给以我们一个启发:这种递推的过程,只用常数个变量而不是通过函数栈来保存所需的所有数据。对于递归我们则要思考的另一个问题,递归过程是否也可以不用进行回溯,不用保存递归调用栈?上面提到了递归调用会保存当前函数的变量返回地址,变量被保存起来时因为在调用自身之后可能会被调用。 例如用递归来描述的计算阶乘的过程:
<span style="font-family:SimSun">function factorial(n){
if(n<=0)
return 0;
if(n ==1)
return 1;
return factorial(n-1)*n;
}</span>
变量n需要被保存下来,一直等到factorial(n-1)的调用返回并计算,最后将计算结果通过返回地址返回到调用factorial(n)的地方。 在这个过程需要保存下变量返回地址,但如果我们把他们作为参数传递给递归调用函数呢?是不是可以不用保存了呢?于是我们改进了一下代码,把当前需要用的变量传递下去:
<span style="font-family:SimSun">function factorial(n,a){
if(n<=0)
return 0;
if(n == 1)
return a;
return factorial(n-1,a*n);
}</span>

相比较之前一般形式的递归代码,有两个不同的地方:
  • 递归调用时,把n当做参数传给了递归函数,无需等待递归调用返回后参与计算。
  • 最终的计算结果在最后一次递归调用后产生,无需回溯。
我们通过这种形式,解决了需要函数回跳才能计算的问题,但最后产生的计算结果仍然需要层层的回调,但这种代码的形式对于普通的递归来说,编译器更容易对其进行优化。这种特殊的递归叫做尾递归,从递归代码形式上看,它自身的调用是函数的最后一个操作。尾递归的目的是为了优化,而优化的目标是减少栈的空间。

尾递归是递归的一种优化
按照尾递归的定义,尾递归就至少必须解决一般递归的两个问题:
  • 不能重复计算
  • 重复利用栈空间
然而尾递归是为编译器优化的目的,所以还要依赖于编译器的实现,如果一种语言不支持尾递归,那么尾递归也就仅仅是个形式上递归了,JavaScript就是这样的语言,因为它无法优化栈空间的利用。以fibonacci为例,这次我们写一个尾递归的版本:
<span style="font-family:SimSun">function fibonacciTailRecursive(n, a, b){
if(n ==0)
return a;
if(n ==1)
return b;
return fibonacciTailRecursive(n-1, b, a+b);
}</span>
> fibonacciTailRecursive(100000,0,1)   RangeError: Maximum call stack size exceeded

看到这个错误,说明JavaScript尾递归版本的代码并没有被优化,所以在这里尾递归仅仅解决第一个问题, 而第一个问题并不是尾递归的专利,我们用动态规划的思想同样可以做到。 那么尾递归如果没有被编译器优化的话,叫这个名字还真是尴尬!

实际上尾递归一直被看作一种编译技巧,特别是对于函数式编程语言来说,尾递归的编译器实现做当做的一种必须的标准,例如Scheme作为一种Lisp方言,并没有类似for,while的语法定义,因此它必须通过一种高效的递归定义来完成实现过程,Scheme的IEEE标准就要求Scheme解释器必须是尾递归的。
---------------全文结束--------------

[参考文献]
1Harold Abelson / Gerald Jay Sussman /.  计算机程序的构造和解释北京:机械工业出版社2004-2.