海归
用一只海龟来引入“递归”，是有一些滑稽，但也没有关系。可能你更喜欢的是海龟而不是无穷的递归调用，那递归长什么样呢？
（一）递归的样子
各种表现，比如这些样子：
- 和尚讲故事
从前有座山，山里有座庙，庙里有个老和尚，老和尚给小和尚讲故事，讲的是从前有座山。。。。
- 沙滩是怎么形成的
A：沙堆是怎么形成的？
B：沙堆是一个沙堆加上一粒沙。
A：那这一个沙堆是怎么形成的？
B：这一个沙堆是一个沙堆加上一粒沙。
A：...
-
吓得我
递归结构1
-
递归函数
f(x) = g(f(x-1))
-
巧妙的衣服
递归结构2
-
谣言成真，那还算造谣吗？
上海一男子因造谣称自己因造谣而被拘留15日而被拘留15日。
- 洋葱的构成
一个洋葱就是带着一层洋葱皮的洋葱。
-
转发通知
递归结构3
这些例子可以看到递归的影子，可以感受到递归的一个特点就是“嵌套”，一层套一层，层层新。正如我说的，一定要用自己的话突出重点地表达你的理解，不要完整或完善，那么，递归是什么？
（二）递归是什么？
递归就是调用自己，调用自己的就是递归，就这么简单。“自己”是什么？“自己”是一个递归结构或算法。
为什么能够调用自己？
之所以能调用自己，是因为子问题也能用原问题的解决办法。递归的设计，就是把问题分解成更小的问题，而且更小的问题也能用原问题的解决办法。在问题规模足够小的时候，把它解决掉，再层层返回，层层组合。
如果非要说一个伟大的思想来突显递归的nb，那就是以退为进，在遇到问题很复杂你解决不了的情况下，退一步，如果退一步还解决不了，就再退一步--没有什么问题是退一步解决不了的，如果有，那就退两步。在退到足够简单的情况下，把它解决，再回归。这个是不是很厉害？
当然你也可以用数学归纳法来考证递归的伟大，但我觉得大可不必，更多情况下，递归只是解决问题的小工具。
那么，这个小工具怎么用起来？走你！
（三）使用递归
使用递归时，有两个要点可以考虑，一是如何调用自己，包括自己返回后怎么处理，二是在什么时候结束递归。
说多无谓，实战出感悟。不考虑性能，看几个问题的递归解决吧。
问题1：输入数字n，打印出1到n的所有整数。
主体：要打印1到n，那先打印1到n-1，再打印一个n就可以了。这个就是主体，只考虑n跟n-1。
结束：在n为1时打印1，并结束递归。
代码示例：
void pr(int n) {
if (n == 1) {
printf("1\n");
return;
}
pr(n-1);
printf("%d\n", n);
}
效果：
打印1到n
问题2：输出“我当然知道 我知道 我知道 我知道 ...我是个sb 这件事 这件事...这件事”，输入n来控制次数。
主体：把“我当然知道”放在递归函数外，因为它不符合同构的原则。先输出“我知道”，再递归到下一层即可。
结束：在递减到0时，结束递归。
收尾：在递归返回后，输出“这件事”。
代码示例：
#include <stdio.h>
void pr(int n) {
if (n == 0) {
printf("[我是sb]");
return;
}
printf("我知道[");
pr(n-1);
printf("这件事]");
}
int main(int argc, char *argv[])
{
printf("我当然知道{");
pr(10);
printf("}\n");
return 0;
}
效果：
我知道
问题3：求二叉树的高度（最长路径）。
主体：左子树与右子树的高度的最大值，加1就是当前树的高度。
结束：没有子树了。
代码示例：
int treeHeight(struct TreeNode* root) {
if (!root) return 0;
int left = treeHeight(root->left);
int right = treeHeight(root->right);
return MAX(left, right) + 1;
}
问题4：求数组中的最大值与最小值。
演示代码：
#include <iostream>
using namespace std;
template<typename T>
void max_min( T a[], int low, int high, T & max, T & min)
{
if ( low == high ) // 只有一个元素不再划分
{
max = min = a[low];
return;
}
else if ( low == high -1 ) // 只有两上元素不再划分
{
if ( a[low] < a[high] )
{
max = a[high];
min = a[low];
}
else
{
max = a[low];
min = a[high];
}
return;
}
int mid = (low + high) / 2;
T max_another;
T min_another;
max_min( a, low, mid, max, min );
max_min( a, mid+1, high, max_another, min_another );
if ( max < max_another )
max = max_another;
if ( min > min_another )
min = min_another;
}
int _tmain(int argc, _TCHAR* argv[])
{
double a[5] = {23.23, 23.45, .3, -89.3, -2.1};
double max, min;
max_min<double>( a, 0, 4, max, min );
cout << "max: " << max << " min: " << min << endl;
return 1;
}
最后，再提一下递归的深度。
每次递归调用都意味着部分数值压入栈中（比如系统维护的下压栈），这是跟迭代的区别。在迭代中每次循环结束时所有局部变量都获得释放，而递归却会不断累计，所以使用递归算法必须考虑它的深度，考虑是否会造成栈溢出，与及对效率造成的影响。
另外，每一次递归调用，问题的规模都应该有所减少，并最终达到终止条件的要求，从而结束递归调用。
至此，递归的入门介绍完毕了。
总结一下，本文介绍了递归的表现、递归的理解与设计，最后举了几个例子并用递归的思路来实现。递归是一个重要的思考问题的思路，希望能帮到你。
ok
网友评论