迭代递归

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

介绍

迭代

迭代（iteration）是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段代码，直到这个条件不再满足。

• for 循环是最常见的迭代形式之一，适合在预先知道迭代次数时使用
• while 循环比 for 循环的自由度更高。在 while 循环可以自由地设计条件变量的初始化和更新步骤
• 嵌套循环是在一个循环结构内嵌套另一个循环结构

总的来说，for 循环更加紧凑，while 循环更加灵活，两者都可以实现迭代结构，可以互相转换。

递归

递归（recursion）是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段：

• 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
• 归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。

而从实现的角度看，递归代码主要包含三个要素：

• 终止条件：用于决定什么时候由“递”转“归”。
• 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
• 返回结果：对应“归”，将当前递归层级的结果返回至上一层。

从计算角度看，迭代与递归可以得到相同的结果，但它们代表两种完全不同的思考和解决问题方式：

• 迭代：“自下而上”解决问题。从最基础步骤开始，然后不断重复或累加这些步骤，直到任务完成
• 递归：“自上而下”解决问题。将原问题分解为更小子问题，这些子问题和原问题具有相同形式。接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）

调用栈

递归每次调用自身时系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。这将导致两方面的结果：

• 函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归通常比迭代更加耗费内存空间。
• 递归调用函数会产生额外开销。因此递归通常比循环的时间效率更低。在触发终止条件前，同时存在 n 个未返回的递归函数，递归深度为 n。

在实际中，编程语言允许的递归深度通常是有限的，过深的递归可能导致栈溢出错误。

尾递归

有趣的是，如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或者解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归（tail recursion）。

• 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用上下文。
• 尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后无须继续执行其他操作，因此系统无须保存上一层函数的上下文。

总结

从本质上看，递归体现了“将问题分解为更小子问题”的思维范式，这种分治策略至关重要：

• 从算法角度看，搜索、排序、回溯、分治、动态规划等许多重要算法策略直接或者间接地应用了这种思维方式。
• 从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分析。

对比

特性	迭代	递归
实现方式	循环结构	函数调用自身
时间效率	效率通常较高，无函数调用开销	每次函数调用都会产生开销
内存使用	通常使用固定大小的内存空间	累积函数调用可能使用大量的栈帧空间
代码结构	代码直观、可读性好	代码结构简洁、清晰
适用问题	适用于简单循环任务	适用于子问题分解，如树、图、分治、回溯等

实例

斐波那契数列

斐波那契数列的定义如下：
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;
}