首页 » 学习JavaScript数据结构与算法(第2版) » 学习JavaScript数据结构与算法(第2版)全文在线阅读

《学习JavaScript数据结构与算法(第2版)》11.1 递归

关灯直达底部

递归是一种解决问题的方法,它解决问题的各个小部分,直到解决最初的大问题。递归通常涉及函数调用自身。

递归函数是像下面这样能够直接调用自身的方法或函数:

function recursiveFunction(someParam){  recursiveFunction(someParam);};  

能够像下面这样间接调用自身的函数,也是递归函数:

function recursiveFunction1(someParam){  recursiveFunction2(someParam);};function recursiveFunction2(someParam){  recursiveFunction1(someParam);};  

假设现在必须要执行recursiveFunction,结果是什么?单单就上述情况而言,它会一直执行下去。因此,每个递归函数都必须要有边界条件,即一个不再递归调用的条件(停止点),以防止无限递归。

11.1.1 JavaScript调用栈大小的限制

如果忘记加上用以停止函数递归调用的边界条件,会发生什么呢?递归并不会无限地执行下去;浏览器会抛出错误,也就是所谓的栈溢出错误(stack overflow error)。

每个浏览器都有自己的上限,可用以下代码测试:

var i = 0;function recursiveFn  {  i++;  recursiveFn;}try {  recursiveFn;} catch (ex) {  alert('i = ' + i + ' error: ' + ex);}  

在Chrome v37中,这个函数执行了20 955次,而后浏览器抛出错误RangeError: Maximum call stack size exceeded(超限错误:超过最大调用栈大小)。在Firefox v27中,函数执行了343 429次,然后浏览器抛出错误 InternalError: too much recursion(内部错误:递归次数过多)。

 根据操作系统和浏览器的不同,具体数值会所有不同,但区别不大。

ECMAScript 6有尾调用优化(tail call optimization)。如果函数内最后一个操作是调用函数(就像示例中加粗的那行),会通过“跳转指令”(jump) 而不是“子程序调用”(subroutine call)来控制。也就是说,在ECMAScript 6中,这里的代码可以一直执行下去。所以,具有停止递归的边界条件非常重要。

 有关尾调用优化的更多相关信息,请访问http://goo.gl/ZdTZzg。

11.1.2 斐波那契数列

回到第10章提到的斐波那契问题。斐波那契数列的定义如下:

  • 1和2的斐波那契数是 1;

  • nn>2)的斐波那契数是(n-1)的斐波那契数加上(n-2)的斐波那契数。

那么,让我们开始实现斐波那契函数:

function fibonacci(num){  if (num === 1 || num === 2){ //{1}    return 1;  }}  

边界条件是已知的,1和2的斐波那契数(行{1})是1。现在,让我们完成斐波那契函数的实现:

function fibonacci(num){  if (num === 1 || num === 2){    return 1;  }  return fibonacci(num - 1) + fibonacci(num - 2);}  

我们已经知道,当n大于2时,Fibonacci(n)等于Fibonacci(n-1)+Fibonacci(n-2)。

现在,斐波那契函数实现完毕。让我们试着找出6的斐波那契数,其会产生如下函数调用:

我们也可以用非递归的方式实现斐波那契函数:

function fib(num){  var n1 = 1,    n2 = 1,    n = 1;  for (var i = 3; i<=num; i++){    n = n1 + n2;    n1 = n2;    n2 = n;  }  return n;}  

为何用递归呢?更快吗?递归并不比普通版本更快,反倒更慢。但要知道,递归更容易理解,并且它所需的代码量更少。

 在ECMAScript 6中,因为尾调用优化的缘故,递归并不会更慢。但是在其他语言中,递归通常更慢。

所以,我们用递归,通常是因为它更容易解决问题。