第六章：递归与分治

一、递归

1. 概念与原理

​定义​：在函数体内调用自身的一种编程技术。

核心机制：每一次调用函数时，系统会在栈区创建一个新的栈帧，用于保存局部变量、参数、返回地址等。

​终止条件（递归出口） ​：

• 必须明确设置，如 if (n == 0) return 1;​
• 每次递归必须向出口靠近（如参数不断减小）

​风险​：若无终止条件或递归不收敛，会导致 ​栈溢出（Stack Overflow） ​。

2. 函数调用过程（包括递归）

​

​压栈​：

• 每调用一次函数，CPU将当前函数的执行现场压入栈中。
• 创建新的局部变量、参数空间。

​跳转​：

• 程序计数器（PC寄存器）跳转至被调函数的入口。

​弹栈​：

• 被调用函数返回后，释放其栈帧，返回到主调函数继续执行。

​工具辅助观察​：

• ​调用堆栈窗口​：显示当前调用链。
• ​黄色箭头​：表示当前正在执行的指令位置。

3. 递归的调试与分析

​压栈过程​：递归调用会创建多个相同函数名但不同参数的栈帧。

​弹栈过程​：从满足终止条件的位置开始逐层返回。

​无限递归示例​：

void f(int i) {
    cout << i << endl;
    f(i+1); // 无终止条件，最终栈溢出
}

​正确写法示例​：

void f(int i) {
    if (i <= 0) return; // 递归出口
    cout << i << endl;
    f(i - 1);           // 向出口靠近
}

二、分治法（Divide and Conquer）

1. 概念

​思想​：把一个大问题分解成结构相同的小问题，逐层解决小问题后再合并结果解决原问题。

​与递归关系​：

• 分治通常通过递归来实现。
• 每一层递归完成一次“分”操作，返回时执行“治”的合并操作。

2. 典型示例：跳台阶问题

问题描述：有 n​ 级台阶，每次可以走1级或2级，问从0级到n级共有多少种走法？

分析过程：

​

​递推关系​：
​f(n) = f(n - 1) + f(n - 2)​
（最后一步是走1级或2级）

​最小问题​：

• ​f(1) = 1​（只能一步到达）
• ​f(2) = 2​（走两次1级或一次2级）

代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
using namespace std;
int f(int n) {
	if (n == 1) {
		return 1;
	}
	else if (n == 2) {
		return 2;
	}
	else {
		return f(n - 1) + f(n - 2);
	}
}
int main() {
	int n;
	scanf("%d", &n);
	printf("%d\n", f(n)); 
	return 0;
}

调试观察：

• ​递归深度​：从 n​ 层层向下压栈直到最小问题，再逐层弹栈。
• ​深度优先特点​：优先完全展开一个分支。
• ​重复子问题​：如 f(3)​ 会被多次计算，时间复杂度是指数级（可通过记忆化优化）。

三、递归 vs 迭代：何时用谁？

维度	递归	迭代
代码可读性	高，接近数学定义	低，需手动维护栈
空间	O(递归深度)	O(1)（循环）或 O(n)（手动栈）
性能	函数调用开销大	无额外开销
适用场景	分治、DFS、树遍历	大规模、深度不可控

四、例题

不连续1的字符

要求：
请计算长度为 $N$ 且 不含连续1 的 01串 的个数。

示例：
当 $N = 3$ 时，答案为 5，因为长度为3的、且不含连续1的01串有：

000, 001, 010, 100, 101

解析：

一、建模

我们定义两个函数：

• $f_0(N)$：表示 以 0 结尾 的长度为 $N$ 的合法 01 串数量；
• $f_1(N)$：表示 以 1 结尾 的长度为 $N$ 的合法 01 串数量；

最终总数为：

$$f(N) = f_0(N) + f_1(N)$$

二、递推关系：

1. 推导 $f_0(N)$：

当前第 $N$ 位是 0，前 $N-1$ 位可以合法地以 0 或 1 结尾；

所以：

$$f_0(N) = f_0(N-1) + f_1(N-1)$$

2. 推导 $f_1(N)$：

当前第 $N$ 位是 1，则第 $N-1$ 位 只能是 0，否则就会有连续的 1；

所以：

$$f_1(N) = f_0(N-1)$$

三、初始条件：

• $f_0(1) = 1$：只有一个合法串 0​；
• $f_1(1) = 1$：只有一个合法串 1​。

四、代码呈现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
using namespace std;
int f0(int n);
int f1(int n);
int f0(int n) {//末尾为零
	if (n == 1) {
		return 1;
	}
	else {
		return f0(n - 1) + f1(n - 1);
    
	}
}
int f1(int n) {//末尾为一
	if (n == 1) {
		return 1;
	}
	else {
		return f0(n - 1);
	}

}
int main() {
	int n;
	scanf("%d", &n);
	printf("%d\n", f0(n) + f1(n));
	return 0;
}