作为一个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数中,我们知道重复计算量会更大。对于这种需要重复计算的子问题,可以把重复计算子问题的答案储存起来,使用时查询,无需计算。这就是动态规划的思想。