最近看到好多人用手机拍递归照,于是我跟着俗气了一把。这张照片不仅满足我的自拍欲望, 也让我对递归充满了敬意!如果用语言来描述拍照时发生的情景的话,那就是:
现实中的我,在拍照片照片中的我,在拍照照片中的我拍的照片中我,在拍照。。。第N重世界中的我,还在拍
用函数递归代码来描述更是直接而又暴力, 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;当函数递归调用的栈深度超多栈的最大限度时就会溢出,例如:上面的a(); 很快就会抛出RangeError: Maximum call stack size exceeded。
setTimeout(function(){console.log((n*2/1024)+"KB")}, 1000);
a();
function a(){
n++;
a();
}
</span>
然而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){虽然在时间得到很大的提高,但是递归的本质并没有什么变化,仍然需要用栈来保存递归调用, 因此在空间上相比fibonacciRecursivily反而额外增加了一个数组,空间复杂度反而有所增加。 这显然不能让人满意,因为我们可以很容易的写出一个更高效的非递归算法:
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>
<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){变量n需要被保存下来,一直等到factorial(n-1)的调用返回并计算,最后将计算结果通过返回地址返回到调用factorial(n)的地方。 在这个过程需要保存下变量和返回地址,但如果我们把他们作为参数传递给递归调用函数呢?是不是可以不用保存了呢?于是我们改进了一下代码,把当前需要用的变量传递下去:
if(n<=0)
return 0;
if(n ==1)
return 1;
return factorial(n-1)*n;
}</span>
<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当做参数传给了递归函数,无需等待递归调用返回后参与计算。
- 最终的计算结果在最后一次递归调用后产生,无需回溯。
尾递归是递归的一种优化
按照尾递归的定义,尾递归就至少必须解决一般递归的两个问题:
- 不能重复计算
- 重复利用栈空间
<span style="font-family:SimSun">function fibonacciTailRecursive(n, a, b){> fibonacciTailRecursive(100000,0,1) RangeError: Maximum call stack size exceeded
if(n ==0)
return a;
if(n ==1)
return b;
return fibonacciTailRecursive(n-1, b, a+b);
}</span>
看到这个错误,说明JavaScript尾递归版本的代码并没有被优化,所以在这里尾递归仅仅解决第一个问题, 而第一个问题并不是尾递归的专利,我们用动态规划的思想同样可以做到。 那么尾递归如果没有被编译器优化的话,叫这个名字还真是尴尬!
实际上尾递归一直被看作一种编译技巧,特别是对于函数式编程语言来说,尾递归的编译器实现做当做的一种必须的标准,例如Scheme作为一种Lisp方言,并没有类似for,while的语法定义,因此它必须通过一种高效的递归定义来完成实现过程,Scheme的IEEE标准就要求Scheme解释器必须是尾递归的。
---------------全文结束--------------
[参考文献][1]Harold Abelson / Gerald Jay Sussman /. 计算机程序的构造和解释. 北京:机械工业出版社,2004-2.