什么是递归算法与递归函数 直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数
递归函数的两个基本要素及递归算法的两个基本部分分别是什么 递归函数的两个要素 递归边界 ，也就是函数的初始值，每一个递归函数都必须具备非递归定义的初始值，否则，递归函数就无法计算。
递归关系式 ，用较小自变量的函数值来表示较大自变量的函数值，它是递归求解的依据，体现分治策略的核心要素。
递归算法的两个基本部分 边界处理部分 ，它是递归出口，决定何时结束递归调用
递归调用部分 ，它实现递归方程或递归操作过程
分治法的设计思想 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之
递归的优缺点和解决方法 优点 结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点 递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
解决方法 在递归算法中消除递归调用，使其转化为非递归算法。
采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。
还要根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间，以达到节省计算时间和存储空间的目的。
用递归解决排列问题(programming) 题目大意 给出一个序列输出全排列
实现思路 我们这里用递归分治的思想来解释。我们知道，如果对于一串长度为n的序列，如果前k个数固定不变，那么全排列总数就是后n-k个数全排列的总数。于是我们就得到了一个可递推的关系：开始时k=0，依次枚举n个数为固定的第一位，于是这时候k=1，那么也就是后n-1个数全排列的结果加上第一位。之后便重复此过程，每次拓展一位，到最后，每个数都划入了固定区，那么便是一种情况，将其输出即可
实现细节 这里主要是要考虑临界细节，我们在实现的过程中head作为非固定区的第一项，那么我们知道刚开始我们在循环中就要枚举从head开始的每一项，这里有个自己与自己交换的操作，意在加入自己作为第一个的情况。
实现代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 #include <bits/stdc++.h> #define INF 0x3f3f3f3 #define maxn 100100 typedef long long ll;using namespace std ;#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++) #define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++) #define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt) #define fulset(x, v) memset(x, v, sizeof(x)); template <class Type >void perm (Type a [],int head , int tail ){ if (head == tail) { for (int i=0 ;i<=tail;i++) cout << a[i]; cout << endl ; return ; } for (int i=head;i<=tail;i++) { swap(a[head], a[i]); perm(a,head+1 ,tail); swap(a[head], a[i]); } return ; } int main () int n; cin >> n; char list [10000 ]; cin >> list ; perm(list , 0 , n-1 ); }
用递归解决整数划分问题(programming) 题目大意： 将正整数n表示为一系列正整数之和，n=n1+n2+….nk，其中，n1–nk为不增序列以防重复计数。这种表示成为n的整数划分，问正整数n有几种划分方法
实现思路 这里的关键在于利用逻辑二分的思路将问题逐渐拆分解决。这个思路其实也是一个很经典的dp思路。在这里，对于一个整数n，我们设将其拆分后所有数都小于等于m，那么显然问题的答案就是当m==n时。对于一般情况n，m，这里我们进行拆分，一类是最大的数恰好等于m，另一类是最大的数小于m。由分析可知，这两种情况是对立事件，也即这两种情况互相没有重合并且包含了所有情况。这么做的目的在于我们可以利用这个缩小问题规模，最后触碰到临界小问题。
实现细节 这里主要是要注意临界状态的判断：首先是当m=1时，必然只有全1的拆分，当m>n时，我们根据题目知道等价于m=n的情况。当n=m时，我们这里要等价于n,m-1的种数+1，不然会造成相减为0无法跳出递归调用
实现代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <bits/stdc++.h> #define INF 0x3f3f3f3 #define maxn 100100 typedef long long ll;using namespace std ;#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++) #define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++) #define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt) #define fulset(x, v) memset(x, v, sizeof(x)); int divd (int n, int m) if (m == 1 ) return 1 ; if (m > n) return divd(n,n); if (m == n) return divd(n,m-1 )+1 ; return divd(n-m,m)+divd(n,m-1 ); } int main () int kk; cin >> kk; cout << divd(kk,kk) << endl ; }
