递归，可以通俗地理解为：无限套娃。

我们都听过：“从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，讲的是，从前有座山，山里……”

这个就是一种递归，先执行自己的部分，然后再调用自己，进行无限循环

1. 定义

在《学习 JavaScript 数据结构与算法（第三版）》书中，对递归的定义为：

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

形式一

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

形式二

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

上述两种形式的递归，都没有基线条件，及没有停止点，会一直递归下去，造成栈溢出的现象。故，一般在使用递归的时候，都会进行条件判断，满足条件之后就跳出递归，避免一直死循环下去。

2. 使用

阶乘

迭代阶乘

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) {
  if (n === 1 || n === 0) {
    return 1;
  }
  return n * factorial(n - 1); // 通过再次调用自身，进行计算
}

每当一个函数被一个算法调用时，该函数会进入调用栈的顶部

如果没有添加用以停止函数递归的调用的基线条件，当出现栈溢出错误时，浏览器会抛出错误

斐波那契数

由 0、1、1、2、3、5、8、13、21、34 等数组成的序列。数 2 由 1 + 1 得到，数 3 由 1 + 2 得到，数 5 由 2 + 3 得到，以此类推。斐波那契数列的定义：

• 位置 0 的斐波那契数是零
• 1 和 2 的斐波那契数是 1
• n（此处 n > 2）的斐波那契数是（n - 1）的斐波那契数加上（n - 2）的斐波那契数

迭代求斐波那契数

function fibonacciIterative(n) {
  if (n < 1) return 0;
  if (n <= 2) return 1;
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) {
    fibN = fibNMinus1 + fibNMinus2;
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}

递归求斐波那契数

function fibonacci(n) {
  if (n < 1) return 0;
  if (n <= 20) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

记忆化

function fibonacciMemoization(n) {
  const memo = [0, 1]; //第1,2个数已经写好了
  const fibonacci = (n) => {
    if (memo[n] != null) return memo[n]; //如果是第1,2个数，直接返回本身
    return (memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)); //存缓存
  };
  return fibonacci(n);
}

3. 速度

从测试上看，迭代的速度会比递归的快很多。

使用递归的好处：

• 代码量少
• 结构清晰，易懂

递归主要是调用函数，需要不断地进行进栈出栈，所以消耗时间较多

具体可查看：《递归为什么那么慢？递归的改进算法》