【算法】递归初阶

学会从宏观的⻆度看待递归。

1. 什么是递归？函数自己调用自己。
2. 为什么会用到递归？

• 本质：在处理主问题时，需要解决子问题，两者的处理方式完全一致。
• 问题 -> 相同的子问题 -> 相同的子子问题…直到子问题不能继续拆分为止。

3. 从宏观角度看待递归！

• 不要在意递归的细节展开图 — 写完代码不要再去纠结递归展开图。
• 把递归函数当成一个黑盒 ---- 赋予这个黑盒一个任务。
• 相信这个黑盒一定能帮助我们完成这个任务。

4. 如何写好一个递归：

• 先找到相同的子问题 -> 确定函数的功能以及函数头的设计。
• 只关心某一个子问题是如何解决的 -> 函数体。
• 不能继续拆分的子问题 -> 递归出口。

1.汉诺塔

1205：汉诺塔问题

解法：递归

这是一道「递归」算法的经典题目，我们可以先从「最简单」的情况考虑：

1. 假设 n = 1，只有一个盘子，很简单，直接把它从 a 中拿出来，移到 c 上。
2. 如果 n = 1 呢？这时候我们就要借助 b 了，因为小盘子必须时刻都在大盘子上面，共需要 3 步（为了方便叙述，记 a 中的盘子从上到下为 1, 2）：

• 1 号盘子放到 b 上。
• 2 号盘子放到 c 上。
• 1 号盘子放到 c 上。

至此，c 中的盘子从上到下为 1号，2号。

3. 如果 n = 3 呢？这是我们需要用到 n = 2 时的策略，将 a 上面的 2 个盘子挪到 b 上，再将最大的盘子挪到 c 上，最后将 b 上的 2 个盘子挪到 c 上。其中转移 2 个盘子的策略正好是 n = 2 的方式。在处理 n − 1 的时候，问题又转化成了相同的子问题，此时就可以用递归帮助我们解决。
4. 由此我们可以类比出 n 为任意值的处理方式：

• 当n > 1 时：将 a 上面的 n - 1 个盘子挪到 b 上，再将最大的盘子挪到 c 上，最后将 b 上的 n - 1 个盘子挪到 c 上就完成了所有步骤。在处理 n − 1 的时候，问题又转化成了相同的子问题，此时就可以用递归帮助我们解决。
• 当 n = 1 时：直接放到目标柱子上。

设计递归函数（从重复子问题入手）：

1. 重复子问题：将 x 个盘子，从 begin 柱子转移到 end 柱子上，其中通过 tmp 柱子作为中转。
2. 具体操作：
   a. 先将 beign 上面 x − 1 个盘子借助 end 转移到 tmp 上。
   b. 再把 begin 最下面一个盘子放在 end 上。
   c. 最后把 tmp 上面 x − 1 个盘子借助 begin 转移到 end 上。

#include<iostream>
using namespace std;int n;
char a, b, c;//将 x 柱子上的 n 个盘子，借助 y 柱子，放到 z 柱子上
void dfs(int n, char x, char y, char z)
{if(n == 0) return;dfs(n - 1, x, z, y);printf("%c->%d->%c\n", x, n, z);dfs(n - 1, y, x, z);
}int main()
{cin >> n >> a >> b >> c;dfs(n, a, c, b);return 0;
}

2.占卜DIY

P10457 占卜DIY

解法：递归

搞清楚题意之后，其实就是一个简单的模拟题。这道题用循环也是可以模拟出来的，但是可以锻炼一下递归解法。整个模拟过程：

1. 抽出第 13 堆最上面的牌 x。
2. 把第 x 堆的最后一张拿出来。
3. 拿到这张牌之后，重复 2 过程，直到拿到 13。

上述三步整个一循环，一直循环 4 次，直到把 13 堆上面的牌拿完。

重复子问题：拿到一张牌 x 之后，把第 x 堆最后一张拿出来。

#include<iostream>
using namespace std;const int N = 15;int n = 13, m = 4;
int a[14][5];int cnt[N]; //cnt[i] = j: 第i堆中还有j张牌没有翻void dfs(int x)
{if(x == 13) return; //翻到K时：递归结束int t = a[x][cnt[x]];cnt[x]--;dfs(t);
}int main()
{for(int i = 1; i <= n; i++){cnt[i] = 4; //最开始有4张牌未翻开for(int j = 1; j <= m; j++){char ch; cin >> ch;if(ch >= '2' && ch <= '9') a[i][j] = ch - '0';else if(ch == 'A') a[i][j] = 1;else if(ch == '0') a[i][j] = 10;else if(ch == 'J') a[i][j] = 11;else if(ch == 'Q') a[i][j] = 12;else if(ch == 'K') a[i][j] = 13;} }for(int i = 1; i <= m; i++){dfs(a[n][i]); //递归4次}int ret = 0;for(int i = 1; i <= n; i++){if(cnt[i] == 0) ret++; //若所有的牌都翻开时，最终结果++}cout << ret << endl;return 0;
}

3.FBI 树

P1087 [NOIP2004 普及组] FBI 树

解法：递归

重复子问题：处理每一棵子树：

1. 确定出该子树的类型。
2. 然后从中间分开，先处理左子树，再处理右子树。
3. 然后打印该子树的类型。

如何快速判断出该子树的类型？因为我们要求的是一段区间内 1 的个数，我们可以利用「前缀和」数组求出这段区间和，然后在查询某段区间时，判断一下此时的区间和：

1. 如果等于区间长度，说明是 I 类型。
2. 如果等于 0，说明是 B 类型。
3. 否则就是 F 类型。

#include<iostream>
using namespace std;const int N = 11;int n;
int f[1 << N]; //前缀和数组void dfs(int left, int right)
{if(left > right) return;//判断类型char ret;int sum = f[right] - f[left - 1];if(sum == 0) ret = 'B';else if(sum == right - left + 1) ret = 'I';else ret = 'F';if(left == right){cout << ret;return;}int mid = (left + right) / 2;dfs(left, mid);dfs(mid + 1, right);cout << ret;
}int main()
{cin >> n;n = (1 << n);for(int i = 1; i <= n; i++){char ch; cin >> ch;int t = 0;if(ch == '1') t = 1;f[i] = f[i - 1] + t;}dfs(1, n);return 0;
}