模板
教程
环境
性能
功能
管理
什么是递归算法:对递归的理解
一、基本概念
递归算法是一种直接或者间接调用自身函数或者方法的算法。Java递归算法是基于Java语言实现的递归算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。递归算法，其实说白了，就是程序的自身调用。它表现在一段程序中往往会遇到调用自身的那样一种coding策略，这样我们就可以利用大道至简的思想，把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。递归往往能给我们带来非常简洁非常直观的代码形势，从而使我们的编码大大简化，然而递归的思维确实很我们的常规思维相逆的，我们通常都是从上而下的思维问题， 而递归趋势从下往上的进行思维。这样我们就能看到我们会用很少的语句解决了非常大的问题，所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。
递归算法解决问题的特点：
1)递归就是方法里调用自身。
2)在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。
在做递归算法的时候，一定要把握住出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的，就是一个条件，当满足了这个条件的时候我们就不再递归了。
二、程序示例
①斐波纳契数列(Fibonacci Sequence)
问题描述：求解Fibonacci数列的第n个位置的值?(斐波纳契数列(Fibonacci Sequence)，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F1=1,F2=1,Fn=F(n-1)+F(n-2)(n>2,n∈N*))。
求解代码：
[java] view plaincopyprint?
public class Fibonacci {
/**
* time:2012.12.2
* author:王金宇
* description:用递归实现斐波那契数列，但是此方法是嫉妒危险的，适用于求解比较小的位置数值
*/
public static void main(String[] args) {
Fibonacci fibonacci=new Fibonacci();
int result=fibonacci.fib(5);
System.out.println(result);
}
public int fib(int index){
if(index==1||index==2){
return 1;
}else{
return fib(index-1)+fib(index-2);
}
}
}
public class Fibonacci {
/**
* time:2012.12.2
* author:王金宇
* description:用递归实现斐波那契数列，但是此方法是嫉妒危险的，适用于求解比较小的位置数值
*/
public static void main(String[] args) {
Fibonacci fibonacci=new Fibonacci();
int result=fibonacci.fib(5);
System.out.println(result);
}
public int fib(int index){
if(index==1||index==2){
return 1;
}else{
return fib(index-1)+fib(index-2);
}
}
}
程序分析：这个实例是非常经典的实例，主要是利用递归实现了Fibonacci数列。这个递归算法的出口是在
[java] view plaincopyprint?
if(index==1 || index==2){
return 1;
}
if(index==1 || index==2){
return 1;
}
这个代码段上，如果程序的index符合条件就会停止进行递归。所以这个程序的运行流程是：
刚才说了这个方法十几度危险的，为什么这么说，原因在于在这个递归里做了冗余的工作，如图，我们在f4里面已经计算了f2，可是f3里有同样计算了f2，以此类推那些冗余的工作，在数值比较小的情况下，计算机还是可以接受的。但是，当求解的数值比较大，它是成指数级增长的，所以不要再递归中做重复的工作。
②n的阶乘
问题描述：求5的阶乘
求解代码：
[java] view plaincopyprint?
public class Factorial_Five {
/**
* time:2012.12.2
* author:王金宇
* description:递归求n的阶乘
*/
public static void main(String[] args) {
Factorial_Five factorial_Five=new Factorial_Five();
int result=factorial_Five.factorial(5);
System.out.println(result);
}
public int factorial(int index){
if(index==1){
return 1;
}else{
return factorial(index-1)*index;
}
}
}
public class Factorial_Five {
/**
* time:2012.12.2
* author:王金宇
* description:递归求n的阶乘
*/
public static void main(String[] args) {
Factorial_Five factorial_Five=new Factorial_Five();
int result=factorial_Five.factorial(5);
