经典算法详解 之 递归算法

递归算法：递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。

递归算法是算法设计中比较常用的一种算法，它的优点在于考虑问题的角度不再局限于过程，而是从整体的角度去思考问题。常见的递归实例有：阶乘，斐波那契数列，汉诺塔等等。

下面我们分别用java语言来书写上述的三个例子：

阶乘：

importjava.io.*;

publicclass Factorial{

publicstatic void main(String[] args) throws IOException {

int n,m;

BufferedReader buf;

buf=new BufferedReader(new InputStreamReader(System.in));

System.out.print("请输入所求的阶乘数：");

n=Integer.parseInt(buf.readLine());

Factorial factorial=new Factorial();

m=factorial.multiply(n);

System.out.println(n+"的阶乘为： "+m);

}

publicint multiply(int n){

//跳出递归条件

if(n==1||n==0){

return1;

}

else{

//子问题分解

returnn*multiply(n-1);

}

}

}

斐波那契数列

importjava.io.*;

publicclass Fibonacci{

publicstatic void main(String[] args) throws IOException {

int n;

BufferedReader buf;

buf=new BufferedReader(new InputStreamReader(System.in));

System.out.print("请输入需要输出的Fibonacci的个数：");

n=Integer.parseInt(buf.readLine());

Fibonaccifibonacci=new Fibonacci();

while(n==0){

System.out.print("您所输入的Fibonacci的个数为0，请重新输入！");

n=Integer.parseInt(buf.readLine());

}

for(inti=1;i<=n;i++){

System.out.print(fibonacci.fib(i)+"");

}

}

publicint fib(int n){

//特殊情况

if(n==0){

return0;

}

else{

//跳出递归条件

if(n==1||n==2){

return1;

}

else{

//子问题分解

returnfib(n-1)+fib(n-2);

}

}

}

}

汉诺塔：

importjava.io.*;

publicclass Hanoi{

publicstatic void main(String args[]) throws IOException{

int n;

BufferedReader buf;

buf=new BufferedReader(new InputStreamReader(System.in));

System.out.print("请输入盘数");

n=Integer.parseInt(buf.readLine());

Hanoihanoi=new Hanoi();

hanoi.move(n,'A','B','C');

}

publicvoid move(int n,char a,char b,char c){

//跳出递归条件

if(n==1){

System.out.println("盘"+n+"由 "+a+" 移至"+c);

}

else{

//子问题分解

move(n-1,a,c,b);

System.out.println("盘"+n+"由 "+a+" 移至 "+c);

//子问题分解

move(n-1,b,a,c);

}

}

}

从上述代码中我们可以总结出，递归使用的一般规律:

1、问题可分解与原问题相似或相近的子问题。

例如：

n的阶乘可以看做是n乘以n-1的阶乘

斐波那契数列的第n个数是第n-1和n-2个数的和

如果要移动n个盘子的汉诺塔，可以看做是：先移动最上面n-1个汉诺塔和最下面盘子等等

总之，找出递归调用的分解是使用递归调用的关键一步

2、问题求解的时候有跳出或结束标志。

例如：

阶乘n的最后一步肯定是n=1

斐波那契数列的最后求和肯定是第一个数和第二个数

汉诺塔中盘子的个数为1的时候等等

注意：有时候在使用递归算法的时候会碰到一些特殊情况，这个时候读者可以根据需要特殊对待。

例如：斐波那契数列的定义规定F(0)=0,这个时候如果需要那么我们就不能用一般的递归来分解这时就需要特殊对待了。