首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >要理解递归,先得理解递归

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

作者头像
我叫刘半仙
发布2018-04-16 16:38:58
1.2K0
发布2018-04-16 16:38:58
举报
文章被收录于专栏:我叫刘半仙我叫刘半仙

       对于一个整天写增删改查的java程序员,厌倦了成天搬砖,所以最近研究了一下递归。首先声明,本人非科班出身,对于刚接触递归就感觉有一种莫名高大上算法的赶脚,本着好奇+梦想成为牛逼攻城狮的想法,就来探一探递归算法的究竟。

1.递归是什么?

       定义:程序调用自身的编程技巧称为递归它分为调用阶段和回退阶段,递归的回退顺序是它调用顺序的逆序。递归使用的是选择结构,对于解决同样问题的孪生兄弟:迭代,它使用的则是循环结构。

       为了加深理解递归,可以多点点该链接:递归.(出口就是右上角x)

       接下来,我们思考一个问题:表达式1+2+3....+100=?要怎么写程序来计算呢?很多人第一反应来使用for循环:

		int sum =0;
		for (int i = 1; i <= 100; i++) {
			sum+=i;
		}
		System.out.println(sum);//5050

       或者二逼青年使用最简洁而且高效的公式(推荐使用,开销最小,且一步到位):

		int start =1;
		int end = 100;
		int sum =(start+end)*end/2;//首项加末项乘以项数除以二
		System.out.println(sum);//5050

       而递归代码如下:

    static  int  recursion(int n){
		if(n==1){//递归出口
			return 1;
		}else{
			return n+recursion(n-1);
		}
	}

通过初体验对比,不难发现以下递归有以下几个要点:

    1.优点:使程序结构更清晰,更简洁,更容易让人理解,

    2.缺点:使用递归调用时,如果过多的调用容易造成java.lang.StackOverflowError即栈溢出和程序执行过慢。这是一个潜在Bug和影响程序执行效率问题,需要谨慎使用。对于互联网这种以速度和效率来维护用户量,不得以用递归时,可以把处理的数据放入缓存,或者直接使用迭代等方式来解决。

    3.规律:递归要有出口,不然成了死循环。解出递归的要点在于求出n-1,求出了n-1才能求解出n,这是为什么呢?

2.递归的执行过程:

    为了搞清楚递归的执行过程,我们配合实例来讲解。在求解阶乘n!=n*(n-1)*(n-2)...*3*2*1时,我们可以写出数学表达式:

       从表达式中可以明显的可以看出:1.递归有出口。2.递归是选择结构。       

    static  int  factorial(int n){
		if(n==0){
			return 1;
		}else{
			return n*factorial(n-1);
		}
	}

       它的调用顺序是怎么样的呢

       或者这样:

调用阶段

回退阶段

          图中红色箭头为调用阶段,绿色箭头为回退阶段。解出递归的要点在于求出n-1,求出了n-1才能求解出n,它思想其实和数学中的归纳本质上是相同的。大家现在是不是可以理解递归回退顺序是它调用顺序的逆序了呢?博主精选了几道题目来加深理解递归:

3.递归算法实例讲解

       以下题目请先思考,并不要急着看代码(最好思考递归和迭代两种方式实现),可能你已经会某些题目,请直接跳过:

      1.题目:有一对兔子,从出生后第3个月起每个月都生一对兔子, 小兔子长到第四个月后每个月又生一对兔子, 假如兔子都不死,问每个月的兔子总数为多少?

分析,这个题目是著名的斐波那契数列:1,1,2,3,5,8,13,21....=Sn = Sn-1+Sn-2

规律是:从第三个数开始,每个数都是前两个数的合。

迭代方式:

		    int month =10; 
	        int sum[]= new int[month] ; //初始化月份数组
	        sum[0] = 1; //第一个月
	        sum[1] = 1; //第二个月
	             
	        for(int i=2;i<=month-1;i++){ 
	            sum[i] = sum[i-1]+sum[i-2]; //第三个月等于前两个月之和
	        } 
	                 
	        System.out.println("第"+month+"个月的兔子总数是:"+sum[month-1]); 

递归方式:

	   static int  recursion(int i){
	        if( i == 1  || i == 2 ){
	            return 1;
	        }
	        else{
	            return  recursion(i-1) +  recursion(i-2);//第三项等于后两项之和
	        }
	    }

      2.题目: 逆序排列字符单词,输入:I love java-->java love I

迭代方式:

static String reverse(String str){
		String[] strs = str.split(" ");
		StringBuilder sb = new StringBuilder();
        //倒叙遍历并拼接空格
		for (int i = strs.length-1; i >= 0; i--) {
			sb.append(strs[i]+" ");
		}
		return sb.toString();
	}

递归方式:

    static String reverse(String s) {
		int i = s.indexOf(" ");//搜索第一次出现" "的位置
	    if (s == null||i == -1) {
	      return s;
	    }
	    return reverse(s.substring(i + 1)) + " " + s.substring(0, i);//每次截取第一个单词放在最后拼接
	}

      3.题目:使用递归来统计字符串String str="hello"的长度,不能使用统计变量(只能用递归求解).

   static int test1(String str){
		if(null==str||str.equals("")){
			return 0;
		}
		String[] strs = str.split("");
		StringBuffer sb = new StringBuffer();//每次截取最后一个字母
		for(int i = 0; i <= strs.length-2; i++)
		{ 
		    sb. append(strs[i]);
		}
		return test1(sb.toString())+1;//每次递归调用+1
	}

      4.题目:实现二分查找算法.  

       二分查找,不断将数组进行对半分割,每次拿中间元素和goal进行比较(前提是数组元素的排序应该是递增或者递减)

    public static void main(String[] args) {
		int [] arr={1,2,5,6,8,9,12,64,78,90};//有序数组
		System.out.println(test(arr,0,arr.length-1,8));//传入数组和数组长度,最后一个是要查找的值
	}
	//递归方式实现
	public static int recursion(int [] arr,int low,int high,int value){
		if(low>high){
			return -1;
		}
		int mid=(low+high)/2;//求中间的值
		if(value==arr[mid]){//如果相等,则找到该值,直接返回
			return mid;
		}else if(value<arr[mid]){//如果要找的值在中间值得左边,则下一次递归开始的右指针指向该次中间值-1
			return recursion(arr,low,mid-1,value);
		}else{////如果要找的值在中间值得右边,则下一次递归开始的左指针指向该次中间值+1
			return recursion(arr,mid+1,high,value);
		}
	}
	//循环方式实现
	public static int test(int [] arr,int low,int high,int value){
		int mid;
		while(high>=low){
			mid=(low+high)/2;
			if(value<arr[mid]){
				high=mid-1;
			}else if(value>arr[mid]){
				low=mid+1;
			}else{
				return mid;
			}
		}
		return -1;//都没找到,则返回-1
	}

      5.题目:求最大公约数和最小公倍数:

	public static void main(String[] args) {
		int x = 100;
		int y =  18;
		System.out.println("最大公约数:"+gcd(x,y));
		System.out.println("最小公倍数:"+lcm(x,y));
	}
	//辗转相除法实现最大公约数
	public static int  gcd(int  x,  int y) {
	    if (y == 0){
	        return x;
        }else{
	        return gcd(y, x % y);//x%y时,如果x<y则返回x,例:4%20=4  5%20=5,迭代之后会把小数放在后面,所以不用做交换
        }
	}
         //最小公倍数   
         public static int lcm(int p,int q){  
               int pq = p * q;  
               return pq / gcd(p,q);  
         } 

      6.题目:杨辉三角

        1         1 1        1 2 1       1 3 3 1      1 4 6 4 1     1 5 10 10 5 1  1 6 15 20 15 6 1 

分析:杨辉三角最本质的特征是,它的两条斜边都是由数字1组成的,而其余的数则是等于它肩上的两个数之和。

	public static void main(String[] args) {
		int n = 7;
		for (int i = 1; i <= n; i++) {
          //双层for循环是为了打印出三角形
			for (int j = 1; j <= n-i; j++) {//每行前面的空格数
				System.out.print(" ");
			}
			for (int j = 1; j <= i; j++) {
				System.out.print(num(i,j)+" ");
			}
			System.out.println();//换行
		}
	}
	public static int num(int x,int y){
		if(y==1||y==x){
			return 1;
		}
			return num(x-1,y-1)+num(x-1,y);//每一个数等于肩上两个数之和
	}

      7.题目:汉诺塔

     接下来就到了递归的经典案例汉诺塔问题,本文就不对汉诺塔游戏规则进行讲解,如果以前没接触过汉诺塔,建议先玩玩汉诺塔游戏,总结一下游戏规律。

现在要把X柱上所有圆盘移动到Z

当移动3个圆盘

当移动6个圆盘

(本图来自于<<程序员的数学>>)

所以可以推出,当n个从x柱,经由y柱中转,移动到z柱(解出n层汉诺塔时),有:

        当n=0时,

                    不用做任何操作

        当n>0时,

                    首先,将n-1个盘子从x借助z移动到y

                    然后,将1个盘子从x移动到z

                    最后,将在中间y上的n-1个盘子借助x移动到z

为了解出n层汉诺塔,需要先使用n-1层汉诺塔的解法。

       从推到过程中我们可以发现:解出递归的要点在于求出n-1,求出了n-1才能求解出n。此外,从数学角度也可以归纳出0,1,3,7,15,63...表达式为:f(n)=2^n  - 1。连接:证明并推导汉诺塔(河内之塔)问题公式

       现在,我们可以给出代码:

	static int t=0;//最少移动次数
	public static void main(String[] args) {
		hanio(3,"x","y","z");
		System.out.println(t);
	}
	 static void  hanio(int n ,String src,String mid,String dest){
		if(n==1){
			System.out.println(src+"-->"+dest);//移动过程
			t++;
		}else{
			hanio(n-1,src,dest,mid);//将n-1个盘子从x借助z移动到y
			hanio(1,src,"",dest);//因为中间柱子没用到,所以可以填""或者填mid,然后将最大的盘子从x直接移动到z
			hanio(n-1,mid,src,dest);//将在中间y柱上的n-1个盘子借助x移动到z
		}
	}

4.总结和展望

       文章开始简单的题目还可以用迭代来求解,随着题目的难度增加,递归对于解决某些问题非常方便,也易于理解。虽然用迭代不是不可以实现,只是同样为了解决某些特性问题,写出迭代的代码花费的时间和难度却比递归高。前文提到,递归和数学中的归纳思想本质上是相同的,都是"将复杂的问题简化"。掌握递归思想的核心就在于"把握结构",因为把握结构是分解整个问题的突破口。

       本文有写的不当之处,还望大家指出.或者有其他解法,欢迎评论区分享交流

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.递归是什么?
  • 2.递归的执行过程:
  • 3.递归算法实例讲解
    •       1.题目:有一对兔子,从出生后第3个月起每个月都生一对兔子, 小兔子长到第四个月后每个月又生一对兔子, 假如兔子都不死,问每个月的兔子总数为多少?
      •       2.题目: 逆序排列字符单词,输入:I love java-->java love I
        •       3.题目:使用递归来统计字符串String str="hello"的长度,不能使用统计变量(只能用递归求解).
          •       4.题目:实现二分查找算法.  
            •       5.题目:求最大公约数和最小公倍数:
              •       6.题目:杨辉三角
                •       7.题目:汉诺塔
                • 4.总结和展望
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档