java培训知识-递归.doc

Java培训专家传智播客递归递归（Recursion）递归：在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。我举个例子来说明这个问题，大家都应该听过这样一个故事： 从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？”。在这里，“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？”这个过程就可以用递归算法来描述。递归作为一种编程技巧在程序设计语言中存在，优点是显而易见的。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 注意： (1) 递归就是在函数里调用自身； (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。递归算法一般用于解决三类问题： (1)数据的定义是按递归定义的。（Fibonacci函数） (2)问题解法按递归算法实现。（回溯） (3)数据的结构形式是按递归定义的。（树的遍历，图的搜索）任何一种技巧都是一把双刃剑，既然有优点，肯定也存在着问题，对此我们也要了解递归的缺点： 递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候才使用递归。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。递归举例例1：计算5!分析：首先我们要明白n！代表什么意思。n! = 123n，假设得到的积是x，x就是n的阶乘。如果采用普通的循环，我们可以用如下函数实现：class Factorial public static void main(String args) System.out.println(getFactorial(5);/求整型数据number的阶乘public static int getFactorial(int number)/由于1乘以任何数等于任何数。所以，定义保存每次乘积结果的变量初始化为1.int sum = 1;/由于1乘以任何数等于任何数。所以，增量从2开始即可。for(int x=2; x1时，结果为 number*(number-1)!在java语言中可用如下代码如下：/求整型数据number的阶乘public static int getFactorial(int number)if(number=1)return 1;elsereturn number*getFactorial(number-1);例2：计算斐波纳契数列的第二十项的值。分析：首先，我们得知道什么的数列是斐波纳契数列。如下：1，1，2，3，5，8，13，21，34，55，89这个数列则称为“斐波纳契数列”，其中每个数字都是“斐波纳契数”。我们要求的是第二十项的值，所以，我们需要观察规律。通过观察可知：从第三个数起，每个数都是前两数之和，那么，采用普通的做法，我们就可以实现求次数列的第二十项的值。class Fibonacci public static void main(String args) System.out.println(fibonacci(20);/求裴波那切数列的第二十项的值public static int fibonacci(int number)/前两个数都是1int first = 1;int second = 1;/用于保存第n项的值int fib = 0;for(int x=3; x2时，结果为 第（number-1）项的值+第（number-2）的值在java语言中可用如下代码如下：/求裴波那切数列的第二十项的值public static int fibonacci(int number)if(number=1 | number=2)return 1;elsereturn fibonacci(number-1)+fibonacci(number-2);通过上面的例子，我们可以看到，递归确实让代码看起来更简洁了。而且还好理解。但是，如果需要循环的次数太多的话，建议不要使用