admin 管理员组文章数量: 887017
递归在搜索算法中使用方法
最近阅读《算法的乐趣》这本书，书中的例子和作者的思考解题思路都让我很受益，给了我很多启发，于是想针对递归的使用方式，结合一些简单的例子，将自己的一些理解写出来供自己和大家在今后学习和工作中参考。
从斐波那契数列说起
递归是每本算法书中必讲解的内容，也是算法设计中的一类重要的设计思想。在搜索算法设计中，递归方式属于一种暴力搜索方法，即通过计算机的高速运算性能对所有的搜索分支都进行判断，取出符合要求的结果，尽管效率较低但简单方便，在很多算法设计中也是有应用。
提到递归，很多初学者或者对其理解不深的程序猿会觉得它很复杂，不容易使用（咱都是一类人），因此希望这篇文章能对学习递归有所帮助。
首先我们可以从斐波拉契数列说起，也是大家比较熟悉或者最先接触递归时的例子，下面是它的代码：
/*Fibonacci: F(n)=F(n-1)+F(n-2)F(0)=F(1)=1
*/#include<stdio.h>
#include<stdlib.h>int Fibonacci(int n);
int main()
{int num,i=0;do{printf("Please input the num(>=1) you want to print of Fibonacci sequences:");scanf("%d",&num);}while(num<1);for(i=0;i<=num;i++)printf("%d ",Fibonacci(i));printf("\n");system("pause");return 0;
}
int Fibonacci(int n)
{if(n<2)return 1;elsereturn Fibonacci(n-1)+Fibonacci(n-2);
}
考虑当我们要计算第N个斐波那契数或者距离某个已知数最近的斐波那契数时，于是就出现递归第一个要素：结束条件。即递归需要有可以终止的结果（找到答案或者没有答案），或者手动设定循环结束的次数，否则会陷入死循环。
递归第二个要素：推进力或者称状态转移驱动。即每次递归过程需要前进而不是保持原状态，前进的方式称为推进力或者驱动力，如斐波那契驱动力是新函数值是前两个函数值之和。
第三个是递归函数，即函数内调用参数不同的自己。
青蛙在想怎么跳台阶
下面再看青蛙跳台阶问题：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个N 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
该问题比较简洁的解法是跳N级的台阶可以变成跳N-1次台阶的跳法加上跳N-2次台阶的跳法（最后一步可以跳1级或者跳2级，最后一步跳1级和前面跳N-1次台阶的跳法，再加上最后一步跳2级和前面跳N-2次台阶的跳法就是跳N级的跳法），即斐波那契数列，这里我们用比较复杂的递归来解，代码如下：
#include <iostream>
static int nCount = 0;
int fnForgStep(int n)
{// 结束条件 n < 0表示不成功， n == 0 表示成功 if(n < 0){return 0;}if(n == 0){nCount++;std::cout << "success!" << std::endl;}// 驱动力 跳一次或者跳两次fnForgStep(n-1);fnForgStep(n-2);return 0;
}int main()
{fnForgStep(10);std::cout << "total " << nCount << " solutions." << std::endl;return 0;
}同上面的斐波那契数列解法，我们发现本题也有这几个要素，结束条件（n<0,n==0），驱动力（青蛙每次跳1级或者2级台阶）。这也是递归不可缺少的步骤。至于在搜素中的应用方式我们下面来看看走迷宫的例子。
迷宫中的暴力美学
下面再讨论搜索问题，迷宫求解：在给定的一个迷宫，求解该迷宫是否能走出并给出所有的解法。
求解迷宫的方式是从起始点开始，四个方向顺序尝试，如果是墙壁则选择另一个方式，能走通则在下一个点再进行四个方向尝试，直至找到出口。这一过程就是搜索路径的过程。
下面是代码：
/*迷宫的解法：当前位置有四个方向，选取任一方向前进，若是终点则返回成功打印路径，若是墙壁或者已走过的路径，则返回上一位置选取另外的方向前进，采用递归的方式遍历全部位置。
*/
#include<iostream>
#include<stdlib.h>using namespace std;
//设计迷宫，‘#’代表墙壁，‘-’代表通道，‘+’代表已走过路径
char maze[8][8]={{'#','#','#','#','#','#','#','#'},{'#','-','-','-','#','#','-','#'},{'#','-','#','-','-','-','-','#'},{'#','-','#','#','-','#','-','#'},{'#','-','-','#','-','#','-','#'},{'#','#',本文标签： 递归在搜索算法中使用方法
版权声明：本文标题：递归在搜索算法中使用方法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732361998h1535479.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论