【J2SE快速进阶】——递归算法

叁歲伎倆 2022-08-06 05:24 192阅读 0赞

###        **递归算法** ###

递归，百度百科对其定义为：程序调用自身的编程技巧。说白了就是一个函数或者过程在执行时会调用自身。

先用一个 “ 求一个数的阶乘 ” 的例子来说明 ：

public class Test {
    	public static void main(String[] args) {
    		System.out.println(Method(3));
    	}
    	public static int Method(int n){
    		if(n==1)
    			return 1;
    		else
    			return n*Method(n-1);				
    	}	
    }

由程序可知，Method()函数的作用为计算参数n的阶乘，当n的值为1时，直接返回结果为1；否则执行else下的语句，重新调用Method()函数，期执行过程如下：

![Center][]

当n=3时，执行else下的return 3\*Method(2)，Method(2)即以2为实参重新调用了函数Method()本身；同理，n=2时，执行else下的return 2\*Method(1)；n=1时，直接返回1。

到了这里会发现，递归可以把一个大型、复杂的问题层层转化为一个与原问题相似的的规模较小的问题来求解，只需要少量的程序代码就可以描述出解题过程需要的多次重复计算，大大减少了程序的代码量。

递归有以下特点：

1、递归实现时，是把一个问题转化为类似的规模较小的问题，而这个新的问题与原问题的解决方法相同，只是处理对象不同，通过多次递归得出最简单的解，然后逐层向上返回调用，得到最终解。；

2、递归要有结束条件，用来终止循环调用，即当满足这个条件时，就不再进行递归，否则一直调用本身，知道满足这个条。（上例中的if(n==1)就是结束条件）

3、虽然递归在一定程度上使代码达到复用，但深层次的递归会涉及到频繁进栈出栈和分配内存空间，所以运行效率比较低，当问题规模较大时，不推荐使用。

4、在递归过程中，每次调用中的参数，方法返回点，局部变量都是存放在堆栈中的，如果当问题规模非常大时，容易造成堆栈溢出。

###        **递归实现的实例** ###

为了加深印象，这里分享几个可以用递归来实现的小例子

1、求1+2+3+……+100 的和

public class Sum {
 	public static void main(String[] args) {
 		System.out.println(sum(100));
 	}
 	public static int sum(int num){
 if(num <= 0){
 	return 0; //当num=0时，循环结束 
 }else{
 	return num + sum(num-1); //调用递归方法 
 } 
 }

2、十进制数转化为二进制数

public class DecimalToBinary {
 	public static void main(String[] args) {
 		DecimalToBinary(118);
 	}
 	public static void DecimalToBinary(int num){
 	if(num ==0){ //当num=0时，循环结束
 	 return;
 	 }else{
 DecimalToBinary(num/2); //调用递归方法
 System.out.print (num%2);
 	 }
 } 
 }

3、计算斐波那契数列

public class Fibonacci{
    	public static void main(String[] args) {
    		System.out.println(fib(4));
    	}
       static int fib(int n)  
    	{  
    	   if(n==0||n==1)  
    	       return n;  	    
    	   else  
    	       return fib(n-1)+fib(n-2);  
    	}  
    }

###        **递归与迭代的区别** ###

一些初学者有时可能会把递归和迭代这两种算法混淆，递归是一个函数（或过程）通过不断对自己的调用而求得最终结果的一个算法，迭代则可以看做循环。

文章开头的例子可以用迭代实现如下：

public class Test {
    	public static void main(String[] args) {
    		System.out.println(Method(3));
    	}
    	public static int Method(int n){
    		int product=1;
    		for(int i=n;i>0;i--){
    			product=product*i;
    		}
    		return product;		
    	}
    }

从代码中可以发现，迭代只是单纯的循环，从i=n一直循环到i=1，最后直接返回最终解product即可；而递归则是把亟待解决的问题转化成为类似的规模较小的问题，通过多次递归得出最简单的解，然后逐层向上返回调用，得到最终解。这里递归就像我们爬山，一个台阶一个台阶爬到山顶后，最终还是要一个台阶一个台阶下山的道理一样。

[Center]: /images/20220806/98649fdffb35499d9a04812a8ca257c5.png