重复执行某个任务在计算机中很常见。迭代和递归是两种基本的重复程序控制结构。

迭代（iteration）

在迭代中，程序会在满足一定条件下重复执行代码，直到条件不再满足。

for 循环

for 循环，时间复杂度是线性关系，与数据输入大小n成正比。适用于预先知道迭代次数的场景。

image-20260509114401775

int for Loop(int n) {
	int res = 0;
	for (int i = 1; i <= n; ++i) {
		res += i;
	}
	return res;
}

while 循环

while 循环中，程序每轮会先检查条件，只有条件为真才会继续执行。while循环适用于自由设计条件变量初始化和更新步骤的场景。

int whileLoop(int n) {
	int res = 0;
	int i = 1;
	while (i <= n) {
		res += i;
		++i;
    i *= 2;
	}
	return res;
}

嵌套循环

可以在一个循环内嵌套循环，这种情况下，函数的操作数与 $n^2$ 成正比。每一次嵌套都会让复杂度升维度。

image-20260509142015212

string nestedForLoop(int n) {
  ostringstream res;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      res << "(" << i << ", " << j << "),";
    }
  }
  
  return res.str();
}

递归（recursion）

递归通过函数调用自身来解决问题，它包含两个阶段：

  1. 递：程序不断调用自身，越往深传入的参数越简单，直到达到终止条件。
  2. 归：触发终止条件后，开始逐层返回，汇聚每一层的结果。

因此，递归算法主要包括三要素：

  • 终止条件：用于决定什么时候由递转归。
  • 递归调用：函数调用自身，传入更简单的参数。
  • 返回结果：将当前递归层级结果返回到上一层。
int recur(int n) {
	// 终止条件
	if (n == 1) {
		return 1;
	}
	// 递归调用
	int res = recur(n - 1);
	// 返回结果
	return n + res;
}

image-20260509143039974

同时存在的递归函数数量，称为递归的深度。上图中，递归深度为n。编程语言一般会对最大递归深度进行限制，过深的递归会导致栈溢出错误。

调用栈

递归函数每次调用自身，系统都会为新开启的函数分配内存存储局部变量、调用地址等函数上下文信息，这些内存空间也被称为栈帧空间。递归通常比迭代更耗费内存，上下文切换导致的时间效率也会相对较低。

尾递归

如果函数在最后一步才进行递归调用，有可能被编译器或解释器优化，让它的空间效率与正常迭代相当。

当函数返回到上一层级的函数后，如果继续执行代码，从而系统需要保存上一层调用的上下文。如果递归调用是函数的最后一步，那么系统后面不再需要执行代码，也不需要保留上下文。这种递归也被称为尾递归。

[!NOTE]

有些编译器不支持尾递归，如python。

递归树

处理“分治”相关的问题时，递归更加直观。以下以斐波那契数列问题为例进行介绍。

int fib(int n) {
	if (n == 1 || n == 2) {
		return n - 1;
	}
	
	return fib(n - 1) + fib (n - 1);
}

每次调用，会产生两个调用分支，最终产生一个层数为n的递归树。

image-20260509144642802

从算法角度看，搜索、排序、回溯、分治、动态规划等算法都直接或间接的应用了将 “将问题分解为更小子问题”的思维范式；从数据结构角度看，递归天然适合处理链表、树、图相关的问题。

使用迭代模拟递归

以下以模拟调用栈来演示递归转为迭代。

int forLoopRecur(int n) {
	stack<int> stack;
	int res = 0;
	// 递归调用
	for (int i = n; i > 0; --i) {
		stack.push(i);
	}
	// 返回结果
	while(!stack.empty()) {
		res += stack.top();
		stack.pop();
	}
	
	return res;
}

总结

递归和迭代代表了两种不同的思考和解决问题的范式。

  • 迭代：自下而上解决问题。从最基础的步骤开始，不断重复和累加这些步骤，知道任务完成。
  • 递归：自下而上解决问题。将原问题分解为更小的子问题，这些问题具有相同的形式。

例如，对于问题 $f(n) = 1 + 2 + … + n$ ，从迭代的视角，可以理解为循环中模拟求和过程，从1累加到n；从递归的视角来看，将问题先分解为子问题 $f(n) = n + f(n - 1)$，直到 $f(1) = 1$终止。