递归

在语言基础部分我们讲：函数自己调用自己称为递归调用，这样的函数则称为递归函数。而递归作为一种算法思想通常是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需要少量的代码就可以描述解题过程所需要的多次重复计算。

递归的思想

问题：求 $n!$

分析： $n! = n * (n - 1)! = n * (n - 1) * (n - 2)!$ 。前面的计算我们可以接着写，直到计算到 $1!$ 为止，而 $1! = 1$ 我们是已知的，问题就变得有解了。

我们发现求 $n!$ 只需要求出 $(n - 1)!$ 即可，这样问题就由 $n$ 的规模转化为了 $n - 1$ 的规模。以此类推，问题的规模逐渐缩小，直到到达终止条件： $1! = 1$ 。

cpp

int fact(int n) {
	if(n == 1) return 1;         // 递归终止条件
	else return n * fact(n - 1); // 递归调用
}

问题：求 $x^{n}$

cpp

int power(int x, int n) { // 求 x 的 n 次方
	if (n == 0) return 1;
	else return x * power(x, n - 1);
}

理解递归时可以借助：1. 递归层次表 2. 递归搜索树。
以求解 $f a c t (5)$ 为例
步骤返回值
fact(5) $↓$ 120 $↑$
fact(4) $↓$ * 5 120 $↑$
fact(3) $↓$ * 4 24 $↑$
fact(2) $↓$ * 3 6 $↑$
fact(1) $↓$ * 2 2 $↑$
fact(1) 1 $↑$

步骤	返回值
fact(5) $↓$	120 $↑$
fact(4) $↓$ * 5	120 $↑$
fact(3) $↓$ * 4	24 $↑$
fact(2) $↓$ * 3	6 $↑$
fact(1) $↓$ * 2	2 $↑$
fact(1)	1 $↑$

构造递归的条件

问题可以分割。分割后的子问题与原问题具有相似的结构，且规模缩小。
问题有终止条件。

常见的递归结构

if...else...结构
前中后结构

if...else...结构

前中后结构

前中后结构也是很常用的一种递归结构。在这种结构中，如果需要返回值，通常是需要引入全局变量的，最后的结果是通过全局变量存储的。

求阶乘代码改写：

cpp

int ans;
void fact(int n) {
    if(n == 1) {
        ans = 1;
		return;
    }            // 前
    fact(n - 1); // 中
    ans *= n;    // 后
}

求 $x^{n}$ 代码改写

cpp

int ans;
void power(int x, int n) {
    if (n == 0) {
        ans = 1;
        return ;
    }
    power(x, n - 1);
    ans *= x;
}

前：递归的终止条件以及需要统计的结果中：递归函数后：需要统计的结果

前中后的后可以省略

例题

求最大公约数

分析：对于正整数 $m, n$ ，其最大公约数 $g c d (m, n) = g c d (n, m % n)$ ，当 $n == 0$ 时 $m$ 即为最大公约数。

cpp

// 辗转相除法
int gcd(int m, int n) {
    if(n == 0) return m;
    else return gcd(n, m % n);
}

分解质因子

输入一个正整数 $n$ ，从小到大输出它的所有质因子。如 36 为 2 2 3 3。

分析：最小的质数是 2， $i$ 从 2 开始枚举，如果是其质因子则输出，同时问题的规模也变为 $\frac{n}{2}$ ，直到 $n$ 等于 1。

cpp

int i = 2;
void solve(int n) {
	if (n == 1) return;
	if (n % i == 0) {
        cout << i << " ";
	    solve(n / i);
	} else {
	    i++;
	    solve(n);
	}
}

元素之和

含有 $n$ 个元素的一维数组 $(n < 25)$ ，又已知一整数 $m$ ，如果能使数组中的若干元素之和等于 $m$ ，则输出 $y e s$ ，否则输出 $n o$

cpp

// 调用方式为 solve(m, n - 1);
bool solve(int m, int idx) {
	if (m == 0) return true;
	// m < 0 时说明还未找到
	// idx = 0 且 m != 0 时说明找完了没找到
	if (m < 0 || idx == 0) return false;

	// 第 idx 个选或是不选
	return solve(m - a[idx], idx - 1) || solve(m, idx - 1);
}

斐波那契数列

cpp

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

YBT 1204 爬楼梯

分析：类比斐波那契数列。第 $n$ 阶台阶可以由之前的第 $n - 1$ 阶或第 $n - 2$ 阶台阶得来，则 $f (n) = f (n - 1) + f (n - 2)$ ，临界条件：当 $n = 1$ 时 $f (1) = 1$ ，当 $n = 2$ 时， $f (2) = 2$ 。

cpp

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

YBT 1205 汉诺塔问题

分析：当 $n = 2$ 时，我们可将 $a$ 上的第一个盘子移到 $c$ 上，再将 $a$ 上的第二个盘子移到 $b$ 上，最后将 $c$ 上的第一个盘子移到 $b$ 上即可，总共三步。当 $n > 2$ 时也是一样，我们把盘子分成两部分：第 $n$ 个盘子，前 $n - 1$ 个盘子，这就和两个盘子的问题一样了。

cpp

#include <iostream>

using namespace std;

int n;

void hanoi(int n, char a, char b, char c) {
	if (n == 0) return ;
	// 前 n - 1 个盘子由 a -> c
	hanoi(n - 1, a, c, b);
	// 第 n 个盘子由 a -> b
	printf("%c->%d->%c\n", a, n, b);
	// 前 n - 1 个盘子由 c -> b
	hanoi(n - 1, c, b, a);
}

int main (){
	cin >> n;
	char a, b, c;
	cin >> a >> b >> c;

	// n 个盘子由 a 移动到  b 上
	hanoi(n, a, b, c);

	return 0;
}

第二类 Stiring 数

第二类 Stirling 数表示把 $n$ 个不同的元素划分为 $m$ 个集合的方案数，要求不能为空集，写作 $s (n, m)$

分析： $s (n, m)$ 可由什么得来？
前 $n - 1$ 个元素已经划分了 $m - 1$ 个集合，第 $n$ 个元素独占第 $m$ 个集合，方案数为 $s (n - 1, m - 1)$
前 $n - 1$ 个元素已经划分了 $m$ 个集合，第 $n$ 个元素放到 $m$ 个集合中的任意一个，方案数为： $s (n - 1, m) \times m$
则 $s (n, m) = s (n - 1, m - 1) + s (n - 1, m) \times m$ ，当 $m = 1 \lor m = n, s (n, m) = 1$ ，当 $m = 0 \lor m > n, s (n, m) = 0$ 。

cpp

int stirling(int n, int m) {
	if (m == 1 || m == n) return 1;
	if (m == 0 || m > n) return 0;
	return stirling(n - 1, m - 1) + stirling(n - 1, m) * m;
}

洛谷 P1028. 数的计算

cpp

int dfs(int n) {
    if (n == 1) return 1;

    int ans = 1;
    for (int i = 1; i <= n / 2; i++) {
        ans += dfs(i);
    }
    return ans;
}

为了避免重复计算导致的时间复杂度过高，可以用记忆化搜索来优化。简单来说就是把已经计算过的结果保存起来，便于日后使用。

cpp

int f[1010];

int dfs(int n) {
    if (n == 1) return 1;

    if (f[n]) return f[n];

    int ans = 1;
    for (int i = 1; i <= n / 2; i++) {
        ans += dfs(i) ;
    }
    return f[n] = ans;
}

洛谷 P1928. 外星密码

cpp

string dfs() {
    string s = "", X;
    char c;
    int D;

    while (cin >> c) { // 读入字符
        if (c == '[') {
            cin >> D;
            X = dfs(); // 递归处理 X
            while (D--) s += X; // X 重复 D 次
        } else if (c == ']') {
            return s;
        } else {
            s += c;
        }
    }

    return s;
}

递归 ​

递归的思想 ​

构造递归的条件 ​

常见的递归结构 ​

if...else...结构 ​

前中后结构 ​

例题 ​

求最大公约数 ​

分解质因子 ​

元素之和 ​

斐波那契数列 ​

YBT 1204 爬楼梯 ​

YBT 1205 汉诺塔问题 ​

第二类 Stiring 数 ​

洛谷 P1028. 数的计算 ​

洛谷 P1928. 外星密码 ​

习题 ​

递归