乐趣区

JavaScript数据结构与算法八递归

jiezi

在之前的文章中我们学习了几种常见的数据结构，接下来我们先了解一下递归思想，为我们后面学习树和图奠定一定的基础。

递归

理解递归

递归是一种解决问题的方法。通俗点来讲，其核心思想就是函数自己调用自己，或者间接调用自身。而如果一直调用自己的话，最终会导致栈溢出从而导致程序崩溃，这是程序员不想发生的问题之一。那么要使用递归，就必须遵循的他的一些注意点。首先要注意的是，每个递归函数都有基线条件，也就是不再发生递归的停止点。还有，既然传递值或者函数到栈空间，那么我们就有好习惯，将不用的或者需要的空间进行返回。也可以这样理解，递归其实就是传递和归还。下面一段简单的代码进行展示。

function understandRecursion(doIunderstandRecursion) {const recursionAnswer = confirm('Do you understand recursion?'); // function logic
  if (recursionAnswer === true) { // base case or stop point
    return true;
  }
  understandRecursion(recursionAnswer); // recursive call
}

understandRecursion(false);//continue
understandRecursion(false);//continue
understandRecursion(true);//stop

一些经典递归算法

阶乘

普通迭代实现 
function factorialIterative(number) {if (number < 0) {return undefined;}
  let total = 1;
  for (let n = number; n > 1; n--) {total  = total * n;}
  return total;
}
递归实现 
function factorial(n) {// console.trace();
    if (n === 1 || n === 0) {return 1;}
  return n * factorial(n - 1);
}

值得注意的是，由于操作系统和浏览器的不同，提供的栈空间不同，也就是栈溢出发生时函数的执行次数不同，并且在 ES6 中提供的是尾调用优化，函数内最后一个操作是调用函数时，会通过跳转指令 jump 而不是子程序调用，导致程序可以一直进行。所以在这里，基线条件是万万不能忘了添加的。

斐波那契数列

迭代实现 
function fibonacciIterative(n){
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) { // n >= 2
    fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}

递归实现 

function fibonacciIterative(n){
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) { // n >= 2
    fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}
记忆化斐波那契数列 
function fibonacciMemoization(n) {const memo = [0, 1];
  const fibonacci = (n) => {if (memo[n] != null) return memo[n];
    return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  };
  return fibonacci(n);
}

总结

迭代版本比递归版本快很多，但是递归版本更容易理解，需要的代码通常更少。使用递归有些算法不用，因为尾调用优化会造成多余的内存消耗，甚至可能会被清除。

退出移动版