java培训知识-递归

《java培训知识-递归》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Java培训专家—传智播客http://java.itcast.cn递归递归（Recursion）递归：在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。我举个例子来说明这个问题，大家都应该听过这样一个故事：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”。在这里，“从前有座山，山里有座庙，庙里有个老和尚，正在给小和

2、尚讲故事呢！故事是什么呢？”这个过程就可以用递归算法来描述。递归作为一种编程技巧在程序设计语言中存在，优点是显而易见的。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。　　注意：　　(1)递归就是在函数里调用自身；(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。　递归算法一

3、般用于解决三类问题：　　(1)数据的定义是按递归定义的。（Fibonacci函数）　　(2)问题解法按递归算法实现。（回溯）　　(3)数据的结构形式是按递归定义的。（树的遍历，图的搜索）任何一种技巧都是一把双刃剑，既然有优点，肯定也存在着问题，对此我们也要了解递归的缺点：　　递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候才使用递归。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。Java培训专家—传智播客http://java.

4、itcast.cn递归举例例1：计算5!分析：首先我们要明白n！代表什么意思。n!=1×2×3×……×n，假设得到的积是x，x就是n的阶乘。如果采用普通的循环，我们可以用如下函数实现：classFactorial{publicstaticvoidmain(String[]args){System.out.println(getFactorial(5));}//求整型数据number的阶乘publicstaticintgetFactorial(intnumber){//由于1乘以任何数等于任何数。所以，定义保存每次乘积结果的变量初始化为1.intsum=1;//由于

5、1乘以任何数等于任何数。所以，增量从2开始即可。for(intx=2;x<=number;x++){sum*=x;}returnsum;}}如果采用递归，我们该如何做呢？思考：你想求n的阶乘，你可以先考虑求n-1的阶乘，然后用n乘以n-1的阶乘。同理n-1的阶乘也可以用n-1乘以n-2的阶乘。而我们知道1的阶乘是1。所以，我们可以用如下规律：当number=1时，结果为1.当number>1时，结果为number*(number-1)!在java语言中可用如下代码如下：Java培训专家—传智播客http://java.itcast.cn//求整型数据number的

6、阶乘publicstaticintgetFactorial(intnumber){if(number==1){return1;}else{returnnumber*getFactorial(number-1);}}例2：计算斐波纳契数列的第二十项的值。分析：首先，我们得知道什么的数列是斐波纳契数列。如下：1，1，2，3，5，8，13，21，34，55，89这个数列则称为“斐波纳契数列”，其中每个数字都是“斐波纳契数”。我们要求的是第二十项的值，所以，我们需要观察规律。通过观察可知：从第三个数起，每个数都是前两数之和，那么，采用普通的做法，我们就可以实现求次数列的第

7、二十项的值。classFibonacci{publicstaticvoidmain(String[]args){System.out.println(fibonacci(20));}//求裴波那切数列的第二十项的值publicstaticintfibonacci(intnumber){//前两个数都是1intfirst=1;intsecond=1;//用于保存第n项的值intfib=0;for(intx=3;x<=number;x++){//第三项开始，每项是前两项之和Java培训专家—传智播客http://java.itcast.cnfib=first+seco

8、nd;fi