什么情况下可以用递归的思想
一个问题可以被分为多个子问题，且子问题之间不冲突，并且多个子问题解决后，问题也被解决了。就可以用递归。
递归的思路
递归首先有一个返回条件，就是说函数肯定不能无限递归下去，那么就要有一个在问题规模较小的时候可以判断的结束条件。
其次递归分为“超级操作”和“微操作”，超级操作就是递归函数本身，而微操作一般都是“递”和“归”中的“归”过程。
如何使用递归函数
这里举个例子，就拿最典型的汉诺塔举例。
汉诺塔问题
问题描述：有从小到大的n个圆盘，圆盘按照从上至下从小到大的顺序套在柱子A上，另有柱子B，C
1.将所有圆盘转移至柱子C
2.圆盘顺序不变且必须时刻保证小圆盘在大圆盘之上
3.一次只能移动一个圆盘
这里将三根柱子分别定义为src，buf，tar。
从src转移至tar。
首先src只有一个圆盘的情况，只需要将src给tar即可，这里记为f(1)操作 。
src有两个圆盘的时候，就要借助buf缓冲，先把最小的放在buf，然后将第二个放到tar，再将最小的从buf拿到tar。这里记为f(2)。
当圆盘数量增加到3个，就可以看做是大规模情况了，那么我们怎么把三个圆盘的问题分解呢，可以把上面两个用f(2)操作，转移到buf，再把第三个移到tar，再对buf上的两个执行f(2)操作，单独转移就是f(1)操作嘛，到这里把整个过程连起来就是f(2),f(1),f(2);
那么4个，5个···n个圆盘，不就是f(n-1) ,f(1), f(n-1)的操作一直执行了吗，当然这里要注意，第一个f(n-1)和第二个f(n-1)他们的函数逻辑不变，但是柱子目标会改变。
这里贴上代码
// 汉诺塔问题
// 问题描述：有从小到大的n个圆盘，圆盘按照从上至下从小到大的顺序套在柱子A上，另有柱子B，C
// 1.将所有圆盘转移至柱子C
// 2.圆盘顺序不变且必须时刻保证小圆盘在大圆盘之上
// 3.一次只能移动一个圆盘
#include <iostream>
#include <vector>
using namespace std;
void move(vector<int>& src, vector<int>& tar) {
int pan = src.back();
src.pop_back();
tar.push_back(pan);
}
void dfs(int i, vector<int>& src, vector<int>& buf, vector<int>& tar) {
if(i == 1) {
move(src, tar);
return;
}
dfs(i - 1, src, tar, buf);
move(src, tar);
dfs(i - 1, buf, src, tar);
}
int main() {
// 有序数组n=10的圆盘
vector<int> vec;
for(int i = 0; i < 10; ++i) {
vec.push_back(i);
}
vector<int> buf, tar;
dfs(10, vec, buf, tar);
for(int i : tar) {
cout << i << ' ';
}
return 0;
}
想不通，仔细一想就晕，怎么办，让我们来治治晕递归。
当然这里我已经会了，也懒得写，直接把我在哪学来的贴上得了。
参考资料：https://www.youtube.com/watch?v=kEWQj2Hb8kc
（这里哔站也有，哔站搜五点七边应该就出来了，再次鸣谢这位大佬）
https://www.hello-algo.com/chapter_divide_and_conquer/hanota_problem/#3