递归和循环

如果我们需要重复多次计算相同的问题，通常可以采用递归或循环两种不同的方法。

• 递归是在一个函数的内部调用这个函数自身
• 循环是通过设置计算的初始值和终止条件，在一个范围内重复运算

对比

递归实现的代码会比较简洁，递归实现要比循环简单得多，但性能不如循环。

递归从尾到头（自上而下）实现，循环从头到尾（自下而上）实现。

递归是函数调用其自身，而函数的调用有时间和空间的消耗。每一次调用函数，都需要在内存中分配空间以保存参数、返回地址、临时变量，而且入栈和出栈都需要时间。

递归中有可能很多计算是重复的，从而对性能带来负面影响。递归的本质是把一个问题分解成两个或者多个小问题。如果小问题内存在重叠的部分，就会存在重复的计算。

递归还有可能引起更严重的问题：调用栈溢出。每个进程的栈的容量是有限的，当递归调用的层级太多时，就会超出栈的容量导致栈溢出。不过，对此 JS 提出了尾递归优化，改善了此问题。

当使用动态规划解决问题时都是用递归的思路分析，但递归分解的子问题中存在大量的重复，因此总是使用自下而上的循环来实现代码。

斐波那契数列问题

斐波那契数列的定义如下：
F(0) = 0; F(1) = 1; F(N) = F(N - 1) + F(N - 2)，其中 N > 1。
求斐波那契数列的第 n 项（即 F(N)）。

// 递归
function fib(n) {
  return n <= 1 ? n : arguments.callee(n - 1) + arguments.callee(n - 2);
}

// 循环
function fib(n) {
  let a = 0,
    b = 1,
    sum;
  for (let i = 0; i < n; i++) {
    sum = a + b;
    a = b;
    b = sum;
  }
  return a;
}

爬楼梯问题

假设你正在爬楼梯，需要 n 阶你才能到达楼顶。
每次可以爬 1 或 2 个台阶，有多少种不同的方法可以爬到楼顶？（n 是一个正整数）

// 递归
function climbStairs(n) {
  return n <= 2 ? n : arguments.callee(n - 1) + arguments.callee(n - 2);
}

// 循环
function climbStairs(n) {
  let a = 1,
    b = 2,
    sum;
  for (let i = 1; i < n; i++) {
    sum = a + b;
    a = b;
    b = sum;
  }
  return a;
}