递归思想的深度理解——汉诺塔问题和青蛙跳台阶问题
递归思想的深度理解——汉诺塔问题和青蛙跳台阶问题
递归是一种重要的编程思想，在解决许多复杂问题时都能发挥重要作用。本文通过两个经典问题——汉诺塔问题和青蛙跳台阶问题，深入浅出地讲解了递归的概念和实现方法。
青蛙跳台阶问题
问题：一只青蛙可以一次跳一级台阶，也可以一次跳两级台阶，如果青蛙要跳n级台阶，共有多少种跳法？
解答：我们可以先找规律，
- 当有一个台阶时，青蛙只有一种跳法。
- 当有两个台阶时，青蛙有两种跳法。
- 当有三个台阶时，青蛙有三种跳法。
- 当有四个台阶时，青蛙有五种跳法。
分析：以一共有三级台阶为例：我们知道，青蛙一开始只能跳一级，或者两级台阶。
- 当青蛙一开始跳一级台阶时，只剩下两级台阶，这样我们就把问题转换成青蛙跳两级台阶有多少种方法，而两级台阶我们在前面已经算过了。
- 当青蛙一开始跳两级台阶时，那么只剩下一级台阶，这样我们就把问题转换成青蛙跳一级台阶有多少种方法，而一级台阶我们在前面也算过了。
最终，我们只需要把一级台阶和两级台阶方法总和加起来就是三级台阶方法的总和。
以此类推，例如，我们要算青蛙跳四级台阶需要多少种方法，同理：
- 当青蛙一开始跳一级台阶时，只剩下三级台阶，这样我们就把问题转换成青蛙跳三级台阶有多少种方法，而三级台阶我们在前面已经算过了。
- 当青蛙一开始跳两级台阶时，那么只剩下二级台阶，这样我们就把问题转换成青蛙跳二级台阶有多少种方法，而二级台阶我们在前面也算过了。
总结：要知道青蛙跳n级台阶需要多少种方法，我们就需要算出其n-1级和n-2级台阶需要多少种方法，而n-1级台阶需要多少种方法，我们就需要算出n-2级和n-3级台阶需要多少种方法，以此类推，……这就是递归思想。
代码展示：
#include<stdio.h>
int main()
{
int n = 5;
int num[5] = { 0 };//因为数据是连续存放的，所以用数组
num[0] = 1;//第一级台阶
num[1] = 2;//第二级台阶
for (int i = 2; i < 5; i++)
{
num[i] = num[i-1] + num[i - 2];
}
printf("%d\n", num[4]);
return 0;
}
汉诺塔问题
题目描述：在经典汉诺塔问题中，有3根柱子及N个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面）。移动圆盘时受到以下限制：
- 每次只能移动一个盘子；
- 盘子只能从柱子顶端滑出移到下一根柱子；
- 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。你需要原地修改栈。
示例1：
输入：A=[2,1,0],B=[],C=[]
输出：C=[2,1,0]
示例2：
输入：A=[1,0],B=[],C=[]
输出：C=[1,0]
提示：
A中盘子的数量不大于14个。
题目链接：https://leetcode.cn/problems/hanota-lcci/description/
首先，我们来提取题目中的关键要素：
- 有A，B，C三根柱子，要将A柱子上的所有盘子，移到C柱子上。
- 一次只能移动一个盘子
- 在移动的过程中，小盘子不可以在大盘子的下面
我们还是一步一步的来，进而寻找规律：
- 当只有一个盘子，直接从A柱子移动到C柱子：
- 当有两个盘子，我们需要将最上面的盘子先从A柱子移动到B柱子，接着将最下面的盘子从A柱子移动到C柱子，最后，将B柱子上的盘子移动到C柱子。
- 当有三个盘子时，我们可以将上面两个盘中当成一个整体，就把问题转换成有两个盘子的时候了，将上面两个盘子从A柱子移动到B柱子上（要想将上面两个盘子移动的B柱子上，又需要将最上面的盘子借助C柱子移动到B柱子上（递归）），接着，将最下面的盘子从A柱子移动到C柱子上，最后将上面的两个盘子从B柱子移动到C柱子上（要想将上面两个盘子移动的B柱子上，又需要将最上面的盘子借助A柱子移动到C柱子上（递归）)。
当有四个盘子时，这个过程就不详细阐述了，同上。
通过上述推论，我们发现，不管有几个盘子，要想把所有盘子从A柱子移动到C柱子上，都需要以上三个步骤，且这三个步骤是完全相同的，我们就可以用递归解决这个问题。
那么，如何写这个题目的代码呢？
关于递归函数头，从整体来看（主问题），我们需要将A柱子上的盘子借助B柱子移动到C柱子上。
void dfs(a,b,c,n);
如何写函数体，我们只需要关注某一个子问题：
dfs(a,c,b,n-1);
x.book();
dfs(b,a,c,n-1);
力扣整体代码：
class Solution {
public:
void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
dfs(a,b,c,a.size());
}
void dfs(vector<int>& a, vector<int>& b, vector<int>& c,int n)
{
if(n == 1)
{
c.push_back(a.back());
a.pop_back();
return;
}
dfs(a,c,b,n-1);
c.push_back(a.back());
a.pop_back();
dfs(b,a,c,n-1);
}
};
（完）