专栏首页Danny的专栏【J2SE快速进阶】——递归算法

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

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/details/42149477

递归算法

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

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

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()函数,期执行过程如下:

       当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){
        <span style="white-space:pre">	</span>if(num ==0){                    //当num=0时,循环结束
               <span style="white-space:pre">	</span>       return;
       <span style="white-space:pre">	</span>        }else{
                      DecimalToBinary(num/2);  //调用递归方法
                      System.out.print (num%2);
       <span style="white-space:pre">	</span>        }
        }  
}

      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即可;而递归则是把亟待解决的问题转化成为类似的规模较小的问题,通过多次递归得出最简单的解,然后逐层向上返回调用,得到最终解。这里递归就像我们爬山,一个台阶一个台阶爬到山顶后,最终还是要一个台阶一个台阶下山的道理一样。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【EJB学习笔记】——JMS和消息驱动Bean

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

    DannyHoo
  • 必备的网络常用测试命令(tracert命令)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

    DannyHoo
  • Java+Oracle实现事务——JDBC事务

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

    DannyHoo
  • LWC 61:738. Monotone Increasing Digits

    LWC 61:738. Monotone Increasing Digits 传送门:738. Monotone Increasing Digits Probl...

    用户1147447
  • 牛客网-剑指offer-3

    这样出现的问题主要是在递归的过程中会出现很多重复的计算,比如我们每次计算第n个的时候,都需要重新计算前面的n-1和n-2,这样每个值其实都会被计算两遍。简单的处...

    小二三不乌
  • 锦囊篇|一文摸懂Glide

    和之前的文章会有一定的不同,这主要是因为Glide自身的源码量导致的问题,因为我是最后写的前言,你会发现在文章刚开始时会代码复制的比较完全,后面就比较零散,而且...

    ClericYi
  • 1019 数字黑洞 (20 分)

    给定任一个各位数字不完全相同的 4 位正整数,如果我们先把 4 个数字按非递增排序,再按非递减排序,然后用第 1 个数字减第 2 个数字,将得到一个新的数字。一...

    可爱见见
  • Leercode 35 Search Insert Position

    Given a sorted array and a target value, return the index if the target is foun...

    triplebee
  • LeetCode 12. Integer to Roman

    ShenduCC
  • 要理解递归,先得理解递归

           对于一个整天写增删改查的java程序员,厌倦了成天搬砖,所以最近研究了一下递归。首先声明,本人非科班出身,对于刚接触递归就感觉有一种莫名高大上算法...

    我叫刘半仙

扫码关注云+社区

领取腾讯云代金券