2.递归的定义：在一个函数的定义中直接或间接地调用本身。
3.递归思想：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
4.递归优点：符合人的思维方式，递归程序结构清晰，可读性高，容易理解。
5.递归缺点：通过调用函数实现，当递归层数过多时，程序的效率低。
6.递归的应用场合： (1)数据的定义形式是递归的。 例如：Fibonaci数列 fib[1] = fib[2] = 1; fib[i] = fib[i - 1] + fib[i - 2]; (i > 2)
例题：B2064 -> P2626 P2626总结： 1.采用记忆化搜索 if(f[x]) return f[x];（切记不可遗漏，不然依旧会在搜索一遍已经保存过的记录； 该语句的作用就是如果已经搜索过，直接返回对应值） 2.mod 2e31 加法mod不影响，在每次加法后面取模即可（但是要注意a + b中a,b要设置成long long 或 unsigned int不然加完就已经溢出了） 3.质因子，一个数的质因子可以直接从i = 2 循环到 i * i <= n 但是要注意 i * i是否会溢出； 可以直接O(n)的原因是一个质因子在之前如果已经被除尽，那么之后所有含有该质因子的数均不可能整除给定的数，否则就与之前的质因子已经除尽相矛盾
(2)数据之间的逻辑关系(即数据结构)是递归的。 例如：树等的定义和操作 (3)一些问题（虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一组操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束）。 例如：汉诺塔问题 例题：P1760 代码1： 40分 测试点2、3AC 测试点1MLE 测试点4、5TLE #include <bits/stdc++.h> using namespace std; #define rep(i,l,r) for (int i = l; i <= r; ++i) int n; long long ans; void hano(int n, char a, char b, char c) { if (n == 1) { ++ans; return ; } hano(n - 1,a,b,c); ++ans; hano(n - 1,b,c,a); } int main() { scanf("%d",&n); hano(n,'A','C','B'); return printf("%lld",ans),0; } 分析原因： 1.本题n <= 15000 递归空间不足；未采用记忆化搜索，时间炸 代码2：40分 测试点2、3AC 测试点1、4、5WA #include <bits/stdc++.h> using namespace std; #define rep(i,l,r) for (int i = l; i <= r; ++i) int n; const int maxn = 15005; long long ans[maxn]; long long hano(int n) { if (n == 1) return ans[1] = 1; if (ans[n]) return ans[n]; return ans[n] = hano(n - 1) * 2 + 1; } int main() { scanf("%d",&n); return printf("%lld",hano(n)),0; } 分析原因： 1.本题n <= 15000，当 n == 63时s = 9223372036854775807 n = 64直接炸long long int 要想拿满分，就要实现高精度 快速幂 注:高精度可以选择python直接实现 代码3: 100分 //code by Fuko_Ibuki //#pragma GCC optimize(3)//去掉O3优化72ms //Optimize“优化” //洛谷提交不能用#pragma GCC optimize(3)会CE #include<bits/stdc++.h> using namespace std; int n; struct hp { int num[20000],len; hp(){ memset(num,0,sizeof num),len = 0;}//sizeof(num)可以写成sizeof num void print() { for (int i = len; i >= 1; --i) putchar(num[i] + '0');//用putchar比printf快 puts(""); } }; hp operator*(hp a, hp b)//高精度乘法 { hp c; for (int i = 1; i <= a.len; ++i) for (int j = 1;j <= b.len; j++) c.num[i + j - 1] += a.num[i] * b.num[j]; //手动模拟得出的规律公式 int i; for (i = 1; i <= a.len + b.len - 1; ++i) { c.num[i + 1] += c.num[i] / 10; c.num[i] %= 10; } for ( ; c.num[i] == 0; i--); //去除前导零 c.len = i;//记录去除前导零后的总长度 return c; } int main() { scanf("%d",&n); hp a,tmp; a.len = tmp.len = 1;//初始化长度为1 a.num[1] = 1; tmp.num[1] = 2; for ( ; n; n >>= 1,tmp = tmp * tmp)//快速幂 if (n & 1) a = a * tmp; a.num[1]--;//公式为2^n - 1;这里实现-1 //为什么可以直接num[1]--？因为num[1] = {2，4，6，8}这些数-1均不会出现非法数字 a.print(); } 总结： 1.一个题目不能只看标签，标签虽然有递归，但是由于本题n很大，递归会导致M/TLE 2.本题答案为2^n - 1可知指数递增十分快，即使是long long int 也不能存储这个数； 因此要编写高精度模板来使用 3.2^n 明摆着可以用快速幂来优化
7.递归设计的要素： (1)在函数中必须有直接或间接调用自身的语句； (2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口（或递归边界）。
8.编写递归算法时，首先要对问题的以下三个方面进行分析： (1)决定问题规模的参数 需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？ (2)问题的边界条件即边界值 在什么情况下可以直接得出问题的解？ (3)解决问题的通式 把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或公式来实现？