递归算法应用

《递归算法应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、递归算法的应用摘要递归做为一种算法在程序设计语言中广泛应用。是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰。递归的主要优点在于：某些类型的算法采用递归比采用迭代算法要更加清晰和简单。例如快速排序算法按照迭代方法是很难实现的。还有其他一些问题，特别是人工智能问题，就依赖于递归提供解决方案。最后，有些人认为递归要比迭代简单递归算法是一种直接或者间接地调用自身的算法。在计算机编写

2、程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：(1)递归就是在过程或函数里调用自身。(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。　(4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。。关键字：递归，程序设计，算法递归算法的应用目录1.绪论

3、11.1问题的提出11.2任务与分析12.0-1背包22.1算法22.2程序23.Hanoi塔43.1算法43.2程序44.棋子移动54.1算法54.2程序65.全排列85.1算法85.2程序96.约瑟夫106.1算法106.2程序11结论13参考文献14递归算法的应用1.绪论1.1问题的提出一个过程或函数直接或间接地调用自己本身称为递归，现在我们以具体例题来分析讲解递归问题。递归的一般思路：把原问题分解为更小的子问题，再从子问题里慢慢寻找原问题的解。解题时首先列出递归表达式，然后用程序语言的方式把

4、他表现出来。往往递归都可转化为循环或者模拟调用栈来实现，但是递归表达更利于理解。1.1.1递归应用递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。(Fibonacci函数)(2)问题解法按递归算法实现。(回溯)(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)1.1.2递归的缺点：递归算法解题的运行效率较低，在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。1.2任务与分析（1）01背包问题的递归算法和程序；（2）n阶hanoi塔

5、的递归算法和程序；（3）棋子移动的递归算法和程序；（4）n个元素全排列的递归算法和程序；（5）约瑟夫问题的递归算法和程序；（6）总结可用递归算法实现的问题。14递归算法的应用1.0-1背包2.1算法find(i,tw,tv)//判定是否放入该物品//输入：当前物品编号i,当前背包重量tw和物品总价值tv//输出：问题解opt[1..n1]iftw+w[i]<=limitWcop[i]←1ifi

6、maxV←tvcop[i]←0iftv-v[i]>maxVifi

7、i+1,tw+a[i].weight,tv);else{for(k=0;kmaxV){if(i

8、,b,c)//Hanoi塔的移动算法//输入：盘子数n,起始、辅助和目标柱a、b、c//输出：Hanoi塔的移动步骤ifn=1output(a,c)elsehanoi(n-1,a,c,b)output(a,c)hanoi(n-1,b,a,c)3.2程序voidhanoi(intn,chara,charb,charc)/*递归函数*/{if(n==1)output(a,c);14递归算法的应用else{hanoi(n-1,a,c,b);/*a借助b到c*/output(