【递归，搜索与回溯算法篇】专题（一） - 递归
文章目录
面试题 08.06. 汉诺塔问题
题目链接：面试题 08.06. 汉诺塔问题
题目描述：
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例 1：
输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]
示例 2：
输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]
提示：
A 中盘子的数目不大于 14 个。
题目解析：
- 小规模问题分析
当N = 1时：直接移动
//将盘子直接从a移动到c a -> c 
当N = 2时:先将最小的盘子从a移到b,再将大盘从a移到c,再将小盘从b移到c。
//先把小盘子从a移动到b a -> b //再把大盘子从a移动到c a -> c //最后把小盘子从b移动到c b -> c 
当N = 3时：先将前两个盘子借助c从a移动到b,再将最大的盘子移动到c，将前两个盘子借助a从b移动到c。
//将前两个盘子从a移动到b(借助c) a -> c a -> b c -> b //将最大的盘子从a移动到c a -> c //将b上面的两个盘子从b移动到c(借助a) b -> a b -> c a -> c 
- 这道题为什么可以使用递归？
解决大问题时出现了相同的子问题，在解决子问题时又出现了相同的子问题。 - 如何编写递归代码？
1.重复子问题 -> 函数头
函数头：将x柱子上的一堆盘子，借助y柱子，转移到z柱子上。n代表盘子的数量void dfs(x , y , z , int n )
2.只关心某一个子问题在做什么 -> 函数体
函数体：
将x柱子上的n-1个盘子借助z柱子放到y柱子上dfs(x , z , y , n-1)
将x柱子最大的盘子放到z柱子上x.back() -> z
将y柱子上的n-1个盘子借助x盘子放到z柱子上dfs(y , x , z , n-1)
当剩最后一个盘子时，直接从a柱子移动到c柱子x.back -> z
代码实现：
classSolution{ public:voidhanota(vector<int>& A, vector<int>& B, vector<int>& C){ dfs(A,B,C,A.size());}voiddfs(vector<int>& A, vector<int
