【阅读笔记：递归】要理解递归，首先要理解递归

爱忘的旺仔

2019-07-09 765 阅读2分钟

什么是递归？

递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。递归通常涉及到函数调用自身。
通常像下面这样能直接调用自身的方法或函数：

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

或者间接调用自身的函数，也是递归函数。

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

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

没个递归函数都必须有基线条件，即一个不再递归调用的条件（停止点），以防止无限递归。

计算一个数的阶乘

5的阶乘为5x4x3x2x1,结果是120。

用迭代来计算阶乘

function factorialIterative(number) {
  if (number < 0) {
    return undefined;
  }
  let total = 1;
  for (let n = number; n > 1; n--) {
    total  = total * n;
  }
  return total;
}
console.log(factorialIterative(5)); // 120

从给定的number开始计算阶乘，并减少n,直到它的值为2。

用递归来计算阶乘

function factorial(n) {
  if (n === 1 || n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}
console.log(factorial(3)); // 6

递归在浏览器中调用站栈的行为是先执行、后调用，下图展示了各个步骤和调用栈中的行为：
如果忘记加上用以停止函数递归调用的基线条件，浏览器就会抛出栈溢出错误

斐波那契数列

斐波那契数列是另一个可以用递归解决的问题。它是由0、1、1、2、3、5、8、13、21、34等数组组成的序列。2由1+1得到，3由1+2得到，5由2+3得到，以此类推

function fibonacci(n){
  if (n < 1) return 0; // 位置0的斐波那契数是零
  if (n <= 2) return 1; // 1和2的斐波那契数是1
  return fibonacci(n - 1) + fibonacci(n - 2);
}

如果我们试着寻找fibonacci（5），下面是调用情况的结果

为什么要使用递归？它更快吗

相比于递归。迭代比递归要更快，但是，递归相对于迭代来说更容易理解，需要的代码通常也更少。

友情链接：