要想先搞DFS，那就先搞明白 递归
先上手一道简单递归题：斐波那契数列
#include <iostream> using namespace std; long int Leo(long int n); int main() { long n; cin>>n;//求Fibonacci数列的第n项 cout<<Leo(n)<<endl; return 0; } long int Leo(long int n) { if(n==0 || n==1) return n; else return Leo(n-1)+Leo(n-2); }
结合图理解：
当数据大时，比如我们我们要求第10个斐波那契数时，
我们会遇到一个问题，比如程序在不断调用自己的过程中，它会不断地重复算
Leo（3），Leo（4），Leo（5）...
那请问有没有一种方式能够直接调用以前计算过的值呢？
巧了，有的，那就是 记忆化
为避免递归时重复计算子问题，可以在子问题得到解决时，就保存结果，再次需要这个结果时，直接返回保存的结果就行了。这种存储已经解决的子问题结果的技术称为“记忆化（Memoization）
优化后的斐波那契数列程序：
#include<bits/stdc++.h> using namespace std; //初始化数组 int a[25] = {0}; //递归函数： int rec(int n){ //递归出口： if(n == 1 || n == 2){ return a[n]; } //记忆化： //比如以前已经算过a[3]=2,那就不必再算，省时 if(a[n] != 0){ return a[n]; } a[n] = rec(n - 1) + rec(n - 2); return a[n]; } int main(){ //初始化数组前两位： a[1] = 1; a[2] = 1; cout << rec(10) << endl; return 0; }
递归的一个应用：全排列算法
给出一些数，生成它们的排列
比如输出： 123 的全排列
我个人在学递归时，喜欢用树状图来分析，结合以下代码，有助于理解：
#include<bits/stdc++.h> using namespace std; int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13}; void dfs(int s, int t){ //递归出口：满足时输出一组排列 if(s == t){ for(int i = 0; i <= t; i++) cout << a[i] << " "; cout << endl; return; } //递归条件: 满足就深入 for(int i = s; i <= t; i++){ swap(a[s], a[i]); dfs(s + 1, t); swap(a[s], a[i]); } } int main(){ int n = 3; dfs(0, n - 1); }
参考：
2022蓝桥杯一站式通关班教程
