众所周知，在一些问题中用递归会使得真个思路变得简单，比如说斐波拉契数列。但同时，简单的思路也会带来比较冗余的压栈开销问题。以下的题只是为了阐述递归分析问题的思路，不讨论复杂度。
1 用递归实现数组求和
int AddAll(int arr[],int begin,int length) //求数组arr，从begin到结束的和 { if (begin == length) return 0; int sum = AddAll(arr, begin+1,length); return sum + arr[begin]; } int main() { int arr[] = {1,2,3,4,5,6 }; int length = sizeof(arr) / sizeof(arr[0]); int sum = AddAll(arr, 0, length); cout << sum << endl; system("pause"); return 0; }总结：在求类似家和问题时，递归会将整个数组分成一部分一部分，我们可以去求从某部分到某部分的和，任意位置都可以。
2 用递归判断字符串是否相等
bool IsEqual(string s1, string s2) { int str1 = s1.length(); int str2 = s2.length(); if (str1 != str2) return false; if (str1 == 0) return true; std::string::iterator it1=s1.begin(); std::string::iterator it2 = s2.begin(); if (*it1 != *it2) return false; return IsEqual(s1.substr(1,str1), s2.substr(1,str2)); } int main() { string s1 = "hello world"; string s2 = "hello worl"; bool ret = IsEqual(s1, s2); cout << ret << endl; system("pause"); return 0; }思路：在这个题中，我们需要判断两个字符串是否相等。按照逻辑我们依次比较就行，在这里需要考虑得程序出口可能就要包括以下几点： 1.如果两个字符串的长度不一样，直接return false； 2.当长度一样时，我们分别取每个字符串的首字母进行比较。当一样时，继续比较下一个字符到整个字符串结尾的那么长的字符串是否相等。依次递归进行比较。
总结：在这类问题中，递归所采用的思想就是把一个大问题不断细分，直到最后可以直接去返回的根源，然后一层一层进行返回。
3 在n个球中，任一取m个（不放回），求有多少种取法
int f(int n, int m) { //a,b,c //ab,bc,ac if (n < m) return 0; if (n == m) return 1; if (m == 0) return 1; //n个里有一个特殊的，取法划分：包不包括这个特殊的 //要么在被取的范围里，要么就不在里面,两种情况 return (f(n - 1, m - 1) + f(n - 1, m)); } int main() { int k = f(10, 3); cout << k << endl; system("pause"); return 0; }思路：中学的时候我们都做过排列组合问题，这个也是一个典型排列组合问题。在这道题里，我们可以将其中三个球标记为特殊的球，那么每次取的时候就会有两种情况，一是包含这种特殊的球，另一种是不包含。如图。
所以我们用递归实现的时候需要考虑到这种情况，每次取球的时候都会发生这种情况，直到m=0。在0个球取0个，只有一种取法。
总结：递归去考虑排列组合问题的时候，一定要抓住特征，找到递归的出口。
4 求n个元素的全排列
void f(string arr,int k) //当前的交换位置 { int len = arr.length(); if (k == (len-1)) { for (int i = 0; i < len; i++) { cout << arr[i] << " "; } cout << endl; } for (int i = k; i < len; i++) { swap(arr[k], arr[i]);//试探 f(arr,k+1); swap(arr[k], arr[i]);//回溯 } } int main() { string arr= "abc"; f(arr,0); system("pause"); return 0; }思路：这个题和上面的题型是比较类似的，但考虑的情况是远比上面多。每一次交换后然后递归出一种情况，接着回溯，使字符串恢复到最初的样子。接着继续排列下一种情况。
