文档章节

Java数据结构与算法(第六章递归)

小风89
 小风89
发布于 2015/10/25 15:29
字数 1339
阅读 229
收藏 5

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

递归是一种方法(函数)调用自己的编程技术。

三角数字

        数字序列 1、3、6、10、15、21、。。。。

        这个数列中的第n项是由第n-1项加n得到了。

        这个序列中数字被称为三角数字,因为他们可以被形象化地表示成对象的一个三角形排列,如图:

    使用循环查找第n项

        第n项的值,比如说第4项(其值为10)。你会如何设计?

int triangle(int n){
    int tatal = 0;
    while(n>0){
        total = total +n;
        --n;
    }
    return total;
}

这个方法循环了n次,total值在第一次循环中加n,在第二次循环中加n-1,如此循环一直到加1,当n减小到0时退出循环。

package com.digui;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Triangle {

    static int theNumber;
    
    public static void main(String[] args) throws IOException {
        System.out.print("Enter a number: ");
        System.out.flush();
        theNumber = getInt();
        int theAnswer = triangle(theNumber);
        System.out.println("Trinagle = "+theAnswer);
    }
    
    public static int triangle(int n)throws IOException{
        if(n==1){
            return 1;
        }else{
            return (n+triangle(n-1));
        }
    }
    
    public static String getString() throws IOException{
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        return br.readLine();
    }
    
    public static int getInt() throws IOException{
        String s = getString();
        return Integer.parseInt(s);
    }
}

//输入输出:
Enter a number: 2
Trinagle = 3

Enter a number: 1000
Trinagle = 500500

递归方法的特征

        所有递归方法都具备的关键特征:

  •         调用自身

  • 当它调用自身的时候,它这样做事为了解决更小的问题。

  • 存在某个足够简单的问题的层次,在这一层算法不需要调用自己就可以直接解答,且返回结果。

    在递归算法每次调用自身的过程中,参数变小(也许是被多个参数秒速的范围变小),这反映了问题变小或变简单的事实。当参数或者范围达到一定的最小值时,将会触发一个条件,此时方法不需要调用自身而可以返回。

递归方法有效率吗?

        调用一个方法会有一定的额外开销。控制必须从这个调用的位置转移到这个方法的开始处。除此之外,传给这个方法的参数以及这个方法返回的地址都要被压入到一个内部的栈里,为的是这个方法可以访问参数值和知道返回到哪里。

        就triangle()这个方法来讲,因为有上述开销二造成的结果,可能while循环方法执行的速度比递归的方法快。

        如果由于递归方法的存在,造成了太大规模的方法调用的话,可能会考虑消除递归,。

        另外一个低效率反映在系统内存空间存储所有的中间参数以及返回值,如果有大量的数据需要存储,这就会引起栈溢出的问题。

        人们常常采用递归,是因为它从概念上简化了问题,而不是因为它本质上更有效率。

数学归纳法

        递归程序设计中数学归纳法。数学归纳法是一种通过自身的语汇定义某事物自己的方法。(语汇也被用于描述证明原理的相关方法。)使用归纳法,可以用数学的方式定义三角数字:

        tri(n) = 1                if n=1

        tri(n)=n+tri(n-1)    if n>1

        用自身来定义某事可能看起来是在转圈子,但是事实上它是完全正确的(假设有一个基值情况)。

阶    乘

        阶乘在概念上和三角数字类似的,只是用乘法取代了加法而已,得到第n个三角数字是通过n加上n-1个三角数字的和,而n的阶乘则是通过n乘以n-1的阶乘来得到的。

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


变 字 位

        这是递归应用的另一种情况。

package com.digui.anagram;
import java.io.IOException;
import redis.digui.Triangle;
public class AnagramApp {
    static int size;
    static int count;
    static char[] arrChar = new char[100];
    
    public static void main(String[] args) throws IOException {
        System.out.print("Enter a word:");
        String intput = Triangle.getString();
        size = intput.length();
        count = 0;
        for (int i = 0; i < size; i++) {
            arrChar[i] = intput.charAt(i);
        }
        doAnagram(size);
    }
    
    public static void doAnagram(int newsize){
        if(newsize==1)
            return;
        for (int i = 0; i < newsize; i++) {
            doAnagram(newsize-1);
        if(newsize==2)
            displayWord();
            rotate(newsize);
        }
    }
    
    private static void displayWord() {
        if(count<99)
            System.out.print(" ");
        if(count<9)
            System.out.print(" ");
        System.out.print(++count+" ");
        for (int i = 0; i < size; i++) {
            System.out.print(arrChar[i]);
        }
        System.out.print(" ");
        System.out.flush();
        if(count%6==0){
            System.out.println("");
        }
    }
    
    public static void rotate(int newsize){
        int j;
        int postion = size-newsize;
        char temp = arrChar[postion];
        for (j = postion+1; j < size; j++) {
            arrChar[j-1] = arrChar[j];
        }
        arrChar[j-1] = temp;
    }
}

输入输出:
Enter a word:cats
  1 cats   2 cast   3 ctsa   4 ctas   5 csat   6 csta 
  7 atsc   8 atcs   9 asct  10 astc  11 acts  12 acst 
 13 tsca  14 tsac  15 tcas  16 tcsa  17 tasc  18 tacs 
 19 scat  20 scta  21 satc  22 sact  23 stca  24 stac


递归的二分查找

    递归取代循环

      

private int recFind(long key,int lowerBound, int upperBound){
    int curIn;
    curIn = (lowerBound + uperBound)/2;
    if(a[curIn]==key)
        return curIn;
    else if(lowerBound>upperBound)
        return nElems;
    else{
        if(a[curIn]<key)
            return recFind(key,curIn+1,uperBound);
        else
            return recFind(key,lowerBound,curIn-1);
    }
}

归并排序

。。。。。。

。。。。。。


小        结

  • 一个递归的方法每次用不同的参数值反复调用自身。

  • 某种参数值使递归的方法返回,而不再调用自身。这种为基值情况。

  • 当递归方法返回时,递归过程通过逐渐完成各层方法实例的未执行部分,而从最内层返回到最外层的原始调用处。



待续。。。

197

























© 著作权归作者所有

小风89
粉丝 19
博文 96
码字总数 96753
作品 0
杭州
高级程序员
私信 提问
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
2018/07/25
0
0
Android--面试中遇到的问题总结(三)

《Android 开发工程师面试指南 LearningNotes 》,作者是陶程,由梁观全贡献部分。大家可以去知乎关注这两位用心的少年。这份指南包含了大部分Android开发的基础、进阶知识,不仅可以帮助准备...

sealin
2017/02/22
0
0
《深入理解 Java 虚拟机 》学习笔记

原文出处:c-rainstorm 第二章 Java 内存区域与内存溢出异常 内存区域 – from 姜志明 对象创建 加载类 若已经在内存中则跳过。 类加载完以后就可以确定对象所需的空间大小 // TODO why? 分配...

c-rainstorm
2018/12/08
0
0
JVM规范系列第6章:Java虚拟机指令集

一条 Java 虚拟机指令由一个特定操作的操作码和零至多个操作所使用到的操作数所构成。 虚拟机指令 = 操作码 + 操作数。 其中,操作码值分别为 254(0xfe)和 255(0xff),助记符分别为 impd...

陈树义
2018/12/19
0
0
最全BAT算法面试100题:阿里、百度、腾讯、京东、美团、今日头条

第一:复杂度估算和排序算法(上) 1) 时间复杂度和空间复杂度 2)认识对数器 3)冒泡排序 4)选择排序 5)插入排序 6)如何分析递归过程的时间复杂度 7)归并排序 8)小和问题 第二:复杂度...

编程SHA
04/25
138
0

没有更多内容

加载失败,请刷新页面

加载更多

有哪些常用的命名git分支实例的例子? [关闭]

现在,我已经使用本地git存储库与我的组的CVS存储库进行了几个月的交互。 我已经制作了一个几乎神经质的分支,其中大部分幸运地合并回我的行李箱。 但是命名开始成为一个问题。 如果我有一个...

javail
4分钟前
1
0
在virtualenv中使用不同的Python版本

我有一个目前使用python 2.5.4运行的Debian系统。 我正确安装了virtualenv,一切正常。 我是否可以将virtualenv与其他版本的Python一起使用? 我编译了Python 2.6.2,并希望将其与一些virtu...

技术盛宴
19分钟前
4
0
保证金术语参考

术语,定义 1.钱包, 余额. ON THE ENCHANGED CONVERGENCE OF STANDARD LATTICE METHODS FOR OPTION PRICING...

MtrS
22分钟前
3
0
x006-函数和模块的使用

函数和模块的使用 在Python中可以使用def关键字来定义函数,和变量一样每个函数也有一个响亮的名字,而且命名规则跟变量的命名规则是一致的。在函数名后面的圆括号中可以放置传递给函数的参数...

伟大源于勇敢的开始
32分钟前
3
0
为什么面试必问线程状态?你的回答满分了吗

看很多同学的面经、网上的面试资料,都不约而同的提到了一个基础问题:“你知道线程有几种状态吗?状态之间的扭转是怎样的?”,有准备的同学都知道有五种:New(新建)、Runnable(可运行)...

Z_J_H
33分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部