递归和分治思想.docx
《递归和分治思想.docx》由会员分享，可在线阅读，更多相关《递归和分治思想.docx（10页珍藏版）》请在冰点文库上搜索。
递归和分治思想
递归和分治思想1
让编程改变世界
Changetheworldbyprogram
递归
妹子，甲鱼哥今天给你讲一个故事吧，从前我有个小弟，酷爱探险，有一次他进了一个山洞，然后又出来，然后又进去，然后又出来，然后又进去，然后又出来。
。
。
。
。
。
后来他很开心~
艹，你说什么呢？
妹子悟性真高^_^
事实上递归就跟鸡生蛋蛋又生鸡的道理一样，只有等哪一天鸡不想生蛋了，做了绝孕手术或者用上了杜蕾斯，这个递归就算结束了。
斐波那契（Fibonacci）数列的递归实现
插句话：
Sierpinski三角形源代码放在论坛，有需要的朋友可以去下载。
斐老跟小甲鱼有个共同爱好，就是老爱拿交配说事儿，不同的是小甲鱼注重过程和细节，斐老更关心结果，下边就有他讲的一个故事：
如果说兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。
假设所有兔子都不会死去，能够一直干下去，那么一年以后可以繁殖多少对兔子呢？
斐波那契数列
斐波那契数列的迭代实现
我们都知道兔子繁殖能力是惊人的，如下图：
斐波那契数列
我们可以用数学函数来定义：
斐波那契数列
课间练习：
假设我们需要打印出前40位斐波那契数列数，我们不妨一起考虑下用迭代如何实现？
斐波那契数列的递归实现
递归事实上就是函数自己调用自己，我们先一起看下代码的实现，然后再来分析：
intFib（inti）
{
if（i<2）
returni==0?
0:
1;
returnFib（i-1）+Fib（i-2）;
}
斐波那契数列
归定义
在高级语言中，函数自己调用和调用其他函数并没有本质的不同。
我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。
不过，写递归程序最怕的就是陷入永不结束的无穷递归中。
切记，每个递归定义必须至少有一个条件，当满足这个条件时递归不再进行，即函数不再调用自身而是返回值。
比如之前我们的Fbi函数结束条件是：
i<2。
对比了两种实现斐波那契的代码，迭代和递归的区别是：
迭代使用的是循环结构，递归使用的是选择结构。
使用递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。
但大量的递归调用会建立函数的副本，会消耗大量的时间和内存，而迭代则不需要此种付出。
递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序。
举个例子，计算n的阶乘n!
n的阶乘
这样我们就不难设计出递归算法：
intfactorial（n）
{
if（0==n）
return1;
else
returnn*factorial（n-1）;
}
假设我们n的值传入是5，那么：
实例分析
题目要求：
编写一个递归函数，实现将输入的任意长度的字符串反向输出的功能。
例如输入字符串FishC,则输出字符串ChsiF。
应用递归的思想有时可以很轻松地实现一些看似不太容易实现的功能，例如这道题。
要将一个字符串反向地输出，童鞋们一般采用的方法是将该字符串存放到一个数组中，然后将数组元素反向的输出即可。
这道题要求输入是任意长度，所以不用递归的话，实现起来会比较麻烦（当然你可以用之前我们讲过的动态申请内存那招）。
我们说过，递归它需要有一个结束的条件，那么我们可以将“#”作为一个输入结束的条件。
voidprint（）
{
chara;
scanf（“%c”,&a）;
if（a!
=‘#’）
print（）;
if（a!
=‘#’）
printf（“%c”,a）;
}
假设我们从屏幕上输入字符串：
ABC#
分治思想
分而治之的思想古已有之，秦灭六国，统一天下正是采取各个击破、分而治之的原则。
而分治思想在算法设计中也是非常常见的，当一个问题规模较大且不易求解的时候，就可以考虑将问题分成几个小的模块，逐一解决。
分治思想和递归算是有亲兄弟的关系了，因为采用分治思想处理问题，其各个小模块通常具有与大问题相同的结构，这种特性也使递归技术有了用武之地。
我们接下来通过实例来讲解。
折半查找算法的递归实现
折半查找法是一种常用的查找方法，该方法通过不断缩小一半查找的范围，直到达到目的，所以效率比较高。
因为这个在《零基础入门学习C语言》等基础教程中已经详细讲解过，小甲鱼这里就通过文字教程简单给大家回顾下算法的主要思路。
从算法的折半查找的过程我们不难看出，这实际上也是一个递归的过程：
因为每次都将问题的规模减小至原来的一半，而缩小后的子问题和原问题类型保持一致。
汉诺塔
一位法国数学家曾编写过一个印度的古老传说：
在世界中心贝拿勒斯的圣庙里，一块黄铜板上插着三根宝石针。
印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。
不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：
一次只移动一片，不管在哪根针上，小片必须在大片上面。
僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
汉诺塔
这其实也是一个经典的递归问题。
我们可以做这样的考虑：
先将前63个盘子移动到Y上，确保大盘在小盘下。
再将最底下的第64个盘子移动到Z上。
最后将Y上的63个盘子移动到Z上。
这样子看上去问题就简单一点了，但是关键在于第1步和第3步应该如何执行呢？
在游戏中，我们发现由于每次只能移动一个圆盘，所以在移动的过程中显然要借助另外一根针才行。
也就是说第1步将1~63个盘子借助Z移到Y上，第3步将Y针上的63个盘子借助X移到Z针上。
那么我们把所有新的思路聚集为以下两个问题：
问题一：
将X上的63个盘子借助Z移到Y上；
问题二：
将Y上的63个盘子借助X移到Z上。
解决上述两个问题依然用相同的方法：
问题一的圆盘移动步骤为：
先将前62个盘子移动到Z上，确保大盘在小盘下。
再将最底下的第63个盘子移动到Y上。
最后将Z上的62个盘子移动到Y上。
问题二的圆盘移动步骤为：
先将前62个盘子移动到X上，确保大盘在小盘下。
再将最底下的第63个盘子移动到Z上。
最后将X上的62个盘子移动到Y上。
升级会员 