作为一个CS学生，必须理解递归函数。这学期的Foundation of Computer里有一章讲到了递归，突然间有了新感悟。
以前理解递归，总会在脑海里模拟递归过程，直到返回为止。但常常内存不够，大脑宕机……T.T
------------------------------------------------------------------------------------------------------------------------------------
举两个例子，一下就明白了：
a[n] = a[n-1] + 1
a[0] = 0;
等差数列！…………一个数的值等于前一个数加1.再加上个初始条件。
F[n] = F[n-1] + F[n-2]
F[0] = 0 F[1] = 1
Fibonacci 数列 ……… 这个数等于前两个数之和。初始条件是前两个数。
还有高中那些个数列啊什么的
a[n] = Aa[n-1] + B , a[0] = xxx。依稀记得求个特征值什么的。
我们知道了递归，其实是定义相关关系。
实践一下：
一、求a[1...n]的最大值
定义max(n)是数组的最大值（注意它虽然是一个递归函数，但实际还是一个值，和前面提到的例子中的F[n],a[n]是一样样的）
max(n) = a[n] 和 max(n-1) 两数较大的那一个
max(1) = a[1]
第一：定义相关关系。
第二：定义截至条件。
相关代码：
int max( int a[], int n){
if( n == 0 ) return a[0];
return a[n] > max( a, n-1 )? a[n]:max(a,n-1);
}
二、生成组合数
a1a2......an选m个数,C(a1a2....an,m)代表选m个数的结果
C(a1...an,m) = a1C(a2...an,m-1) + a2C(a3...an,m-1) +...+ a[n-m+1]C(an-m+2...an,m-1)
截至条件：没有可能时返回,即, 数列长度小于m或者m<=0
举例来说: 1 2 3 4选3个数的组合，等于 1{2 3 4 选2个数的组合} + 2{3 4 选2个数的组合} + 3 { ... 这里没有选择就返回了 }。
其中
2 3 4选2个数的组合，等于2{3 4选1个数的组合} + 3{4 选1个数的组合}。
3 4选2个数的组合，等于3{4 选1个数的组合}。
……（不展开了）
所以1 2 3 4选3个数的组合等于
1{2 3，2 4} + 2{ 3 4 } = 1 2 3 + 1 2 4 + 2 3 4
相关代码：
vector<vector<int>> cat(vector<vector<int>> a, vector<vector<int>> b){ vector<vector<int>> ret; if (!b.size()) return a; if (!a.size()) return b; for (auto itA : a){ for (auto it : b){ vector<int> viNew = itA; for (auto it2 : it){ viNew.push_back(it2); } ret.push_back(viNew); } } return ret; } vector<vector<int>> comb(vector<int> &a, int m, int pos/* start pos,0 */, map<pair<int, int>, vector<vector<int>>>&result/* NULL */){ vector<vector<int>> ret; if (a.size() - pos < m || m <= 0){ return ret; } for (int i=pos; a.size() - i >= m; i++){ vector<vector<int>> aVvi; aVvi.push_back(vector < int > {a[i]}); aVvi = cat(aVvi, comb(a, m - 1, i + 1, result)); for (auto it : aVvi){ ret.push_back(it); } } return ret; }
总结一下，设计递归函数一要理出相关关系。二要设置截至条件。
多说一句，相关关系实际是问题与子问题的关系，可能会重复计算，比如在生成组合数的例子中，我们看到绿色部分被重复计算了两次。而在寻找Fibonacci数中，我们知道重复计算量会更大。对于这种需要重复计算的子问题，可以把重复计算子问题的答案储存起来，使用时查询，无需计算。这就是动态规划的思想。