精华内容
下载资源
问答
  • java 递归程序实现

    千次阅读 2018-11-11 20:14:15
    java 递归程序实现 本文我们介绍编程语言的一个核心概念————递归。介绍递归功能特性,以及如何使用递归解决不能类型问题。 1. 理解递归 1.1. 递归定义 java中函数调用机制支持方法可以调用自身,这种功能...

    java 递归程序实现

    本文我们介绍编程语言的一个核心概念————递归。介绍递归功能特性,以及如何使用递归解决不能类型问题。

    1. 理解递归

    1.1. 递归定义

    java中函数调用机制支持方法可以调用自身,这种功能称为递归。举例,我们计算求和函数:

    public int sum(int n) {
        if (n >= 1) {
            return sum(n - 1) + n;
        }
        return n;
    }
    

    递归函数有两个主要前提:

    • 终止条件——当一定条件满足时,函数返回特定值,不再递归调用
    • 递归调用——函数调用自身,其输入值更接近终止条件

    每次递归调用都会在jvm栈内存空间中增加栈帧,因此我们不注意递归深度,可能会发生栈内存溢出错误。 我们可以利用尾递归优化进行规避。

    1.2. 尾递归VS头递归

    当递归调用是执行函数的最后部分则称为尾递归,反之为头递归。我们现在通过尾递归方式实现上面的示例:

    public int tailSum(int currentSum, int n) {
        if (n <= 1) {
            return currentSum + n;
        }
        return tailSum(currentSum + n, n - 1);
    }
    

    使用尾递归,递归调用是执行方法中最后需要执行的内容,在当前方法中不再有其他内容需要去执行。因此,理论上无需存储当前函数的栈帧。所以编译器能利用这点优化内存,但java编译器暂时没有针对尾递归进行优化。

    1.3. 递归VS迭代

    递归可以帮助简化解决负责问题,且代码更简洁、可读。但通常需要更多的栈内存以及增加每次递归调用。作为替代方案,能使用递归解决的问题,也可以使用迭代方式实现。下面通过迭代方式实现上面求和的示例:

    public int iterativeSum(int n) {
        int sum = 0;
        if(n < 0) {
            return -1;
        }
        for(int i=0; i<=n; i++) {
            sum += i;
        }
        return sum;
    }
    

    相比于递归,迭代方法性能更好。但迭代更复杂,相比于递归更难理解。例如:遍历二叉树时两种方法对比很明显。

    在头递归、尾递归以及迭代方法中选择最佳方案,取决于特定问题和情况。

    2. 示例实战

    下面我们通过示例使用递归解决几个问题。

    2.1. 求10的n次方

    假如我们需要求10 的n次方。输入为n。通过递归方式实现。首先技术10 的 (n-1)次方,然后乘以10。然后计算10 的 (n-1)次方,即为10 的 (n-2)次方乘以10,以此类推,直到计算(n-n)次方,值为1。java实现代码如下:

    public int powerOf10(int n) {
        if (n == 0) {
            return 1;
        }
        return powerOf10(n-1) * 10;
    }
    

    2.2. 求斐波那契数列的第n个元素值

    从0和1开始,斐波那契数列中每个元素是前两个元素之和:0,1,1,2,3,5,8,13,21,34……
    所以,给定数值n,我们的问题是求第n个元素。使用递归方案,我们需要考虑终止条件以及递归调用。
    还好,两种都非常简单。求n个元素值,只要先求f(n) = f(n-1) + f(n-2) (递归调用)。同时 f(0) = 0 和 f(1) = 1 (终止条件)。那么定义递归方法就比较简单:

    public int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }
    

    2.3 十进制转二进制

    下面我们通过递归方法实现十进制转二进制问题。需求是输入十进制数n,输出二进制字符串。
    方法为十进制数除以2,记录余数继续用商除以2。一直除直到商为0.然后使用倒叙写出所有余数,就获得结果。
    因此,我们的问题是写一个方法按照相反的顺序返回这些余数:

    public String toBinary(int n) {
        if (n <= 1 ) {
            return String.valueOf(n);
        }
        return toBinary(n / 2) + String.valueOf(n % 2);
    }
    

    2.4 计算二叉树高度

    二叉树高度定义为从根到最深叶子节点的边数。我们的问题是计算给定二叉树的高度值。
    一个简单方法是查找最深的叶子,然后计算其到根的边数。使用递归的方案实现,我们重新描述二叉树高度定义————求二叉树中左分支和右分支中最大的高度,然后加一。如果根没有左分支和右分支,其高度为0.

    代码实现为:

    public int calculateTreeHeight(BinaryNode root){
        if (root!= null) {
            if (root.getLeft() != null || root.getRight() != null) {
                return 1 + 
                  max(calculateTreeHeight(root.left), 
                    calculateTreeHeight(root.right));
            }
        }
        return 0;
    }
    

    通过示例,我们看到通过递归方式解决一些问题非常简单。

    3. 总结

    本文我们介绍了java中递归的概念,并演示了几个简单示例。

    展开全文
  • 以下是一个Java程序,用于线性查找数组中的元素。示例importjava.util.Scanner;publicclassSearchingRecursively{publicstaticbooleansearchArray(int[]myArray,intelement,intsize){if(size==0){returnfalse;}if...

    以下是一个Java程序,用于线性查找数组中的元素。

    示例import java.util.Scanner;

    public class SearchingRecursively {

    public static boolean searchArray(int[] myArray, int element, int size){

    if (size == 0){

    return false;

    }

    if (myArray[size-1] == element){

    return true;

    }

    return searchArray(myArray, element, size-1);

    }

    public static void main(String args[]){

    System.out.println("输入所需的数组大小: ");

    Scanner s = new Scanner(System.in);

    int size = s.nextInt();

    int myArray[] = new int [size];

    System.out.println("逐一输入数组的元素 ");

    for(int i=0; i

    myArray[i] = s.nextInt();

    }

    System.out.println("输入要搜索的元素: ");

    int target = s.nextInt();

    boolean bool = searchArray(myArray, target ,size);

    if(bool){

    System.out.println("Element found");

    }else{

    System.out.println("Element not found");

    }

    }

    }

    输出结果输入所需的数组大小:

    5

    逐一输入数组的元素

    14

    632

    88

    98

    75

    输入要搜索的元素:

    632

    Element found

    展开全文
  • 一个java递归程序

    2011-06-25 12:18:06
    自己写的一个递归程序,难得写一次递归的程序,拿出来晒晒 题目: 输入: 8 --错误的数 5 --将下边数字累加得总数 2 3 4 1 --总数为5+2+3+4+1=15 0 --0为结束标志 输出: 1 2 4 --1+2+4=7 7+8=15 ...

    自己写的一个递归程序,难得写一次递归的程序,拿出来晒晒

    题目:

    输入:

    8   --错误的数
    5   --将下边数字累加得总数
    2
    3
    4
    1   --总数为5+2+3+4+1=15
    0   --0为结束标志

    输出:

    1 2 4   --1+2+4=7    7+8=15
    2 5      --2+5=7        7+8=15
    3 4      --3+4=7        7+8=15

     

    import java.util.Arrays;
    import java.util.Scanner;
    
    public class LastNumber {
    
    	private static final int MAX=100;
    	private static int[] tnum;
    	private static int[] num;
    	public static void main(String[] args) {
    		int mis;
    		int total = 0;
    		int last = 0;
    		int count = 0;
    		tnum = new int[MAX];
    		Scanner sc = new Scanner(System.in);
    		mis = sc.nextInt();
    		while(true){
    			tnum[count]=sc.nextInt();
    			if(tnum[count]==0)break;
    			total+=tnum[count];
    			count++;
    		}
    		num = new int[count];
    		for(int i=0;i<count;i++)
    			num[i] = tnum[i];
    		Arrays.sort(num);
    		last = total-mis;
    		for(int i=0;i<num.length;i++)
    			find_last(num,i,0,last,"");
    	}
    	
    	public static void find_last(int[] a,int cur,int total,int last,String pix){
    		total+=a[cur];
    		if(total==last){
    			System.out.println(pix+a[cur]);
    		}else if(total<last){
    			for(int i=1;i<a.length-cur;i++)
    				find_last(a,cur+i,total,last,pix+a[cur]+" ");
    		}
    		
    	}
    }
    
    展开全文
  • 一个Java递归程序

    2013-08-02 15:47:00
    使用递归, 于是我变写出了下面的代码:   /** * 输入一个整数,求这个整数中每位数字相加的和 */ public static int f( int n){ if (n ){ return n; } else { int a=n/10 ; int b=...

      先来没事搜了一些面试题来做,其中一道:输入一个整数,求这个整数中每位数字相加的和?

    思考:1.如何或得每一位数:假如是1234,   1234%10=4,得到个位;(1234/10)%10=3得到十位,(1234/100)%10=2得到百位,(1234/1000)%10=1得到千位。

            2.既然是输入一个数,那么位数不确定。我们就不好用去意义判断去除以10、100或者一千,

        这时我的大脑暗示我使用递归,于是我变写出了下面的代码:

     

    /**
         * 输入一个整数,求这个整数中每位数字相加的和
         */
        public static int f(int n){
            if(n<10){
                return n;
            }else{
                int a=n/10;
                int b=n%10;
                return b+=f(a);
            }
        }
        @Test
        public void t() {
            int result=f(1234);
            System.out.println(result);
    
        }

     

    运行结果:10 。 搞定

     

             

    转载于:https://www.cnblogs.com/demingblog/p/3232769.html

    展开全文
  • 我们发现中都是一些条件只有满足这些条件了才...课前准备 云课堂APP 班级二维码 前情回顾 方法的嵌套调用 1方法嵌套调用的写法 2方法嵌套程序的流程执行 教学目标的确定 通过汉诺塔小游戏程序了解java递归的编程思想和
  • Java写一个简单的递归程序递归的定义递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决。递归的要素自定义递归函数,并确定函数的基本功能例如Java从键盘输入一个数,求输入这...
  • Java递归程序

    2018-05-07 22:10:46
    一个阶乘的递归程序 public class Diguidiaoyong_jiecheng { public static void main(String[] args) { System.out.println("输入整数求阶乘:"); Scanner scanner = new Scanner(System.in); int ...
  • java_递归程序

    2020-06-10 15:22:51
    递归程序设计 实验内容: 用递归方法设计下列各题,并给出每道题目的递归出口(递归结束的条件)和递归表达式。同时考虑题目可否设计为非递归方法,如果可以,设计出非递归的算法。 1.一个人赶着鸭子去每个村庄卖,每...
  • 掌握递归程序转换为非递归程序的方法。二、实验内容用递归方法设计下列各题,并给出每道题目的递归出口(递归结束的条件)和递归表达式。同时考虑题目可否设计为非递归方法,如果可以,设计出非递归的算法。1.一个人赶...
  • java 递归程序

    2019-01-09 11:30:50
    import java.util.ArrayList; public class Reursion { public static void main(String[] args) { java.util.List<Person> list=new ArrayList<>(); Person p1=new Person("B","A"); ...
  • 的函数(2)再结合组合数公式,求组合数程序流程图源程序代码package Zuote;import java.math.BigInteger;import java.util.Scanner;public class Zuoye1 {public static void main(String args[]){Sca...
  • Java中的递归什么是递归?函数直接或间接调用自身的过程称为递归,相应的函数称为递归函数。...在递归程序中,给出了基本情况的解,大问题的解用小问题表示。int fact(int n){if (n < = 1) // base casereturn...
  • java写一个简单的递归程序递归的定义递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决。递归的要素自定义递归函数,并确定函数的基本功能例如java从键盘输入一个数,求输入这...
  • 什么是递归递归就是一个程序或函数在其中定义或说明有之间或者间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个原问题相似的规模较小的问题来求解,递归策略只需要少量的程序就可以描述出解题过程...
  • 这就是递归二、为什么要用递归递归的目的是简化程序设计,使程序易读三、递归的弊端:尽管非递归函数效率高,但较难编程,可读性较差。递归函数的缺点是添加了系统开销,也就是说,每递归一次,栈内存就多占用一截...
  • 下面是递归冒泡排序的Java程序示例importjava.util.Arrays;publicclassDemo{staticvoidbubble_sort(intmy_arr[],intlen_arr){if(len_arr==1)return;for(inti=0;iif(my_arr[i]>my_arr[i+1]){inttemp=my_arr[...
  • 在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解.递归的分类:递归分为两种,直接递归和间接递归。直接递归称为方法自身调用自己。间接递归可以A方法调用B方法,B...
  • 1.递归作为一种算法在程序设计语言中广泛应用,是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。2.递归算法一般用于解决三种问题:1)数据的定义是按递归定义的。( Fibonacci(斐波那契)函数)。...
  • 这是一个程序,读取信息网站为以前的格式,它使用...java中执行程序如何终止递归?public class NewClass {static String levels[] = { "div.col-md-9 li a", "div#sidebar ul li a" };static String links = "";pri...
  • 创建java递归的方法:首先创建明确的递归结束条件;...创建java递归的方法:程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或...
  • Java写一个简单的递归程序递归的定义递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决。递归的要素自定义递归函数,并确定函数的基本功能例如Java从键盘输入一个数,求输入这...
  • Java递归

    2021-01-11 22:41:08
    无论在哪里相信大家都听说过递归,我也是个初学者,一开始我也是看不懂的,后来才慢慢看懂,现在我就来记录一下我所了解的Java递归是什么。 递归:程序调用自身的编程技巧称为递归(recursion),它做为一种算法在...
  • Java程序使用递归来反转句子在此程序中,您将学习使用Java中的递归循环来反转给定的句子。示例:使用递归反转句子publicclassReverse{publicstaticvoidmain(String[]args){Stringsentence="Gowork";Stringreversed=...
  • 在这一小节中,将学习如何以递归方式删除java中的非空...下面将递归地使用delete()函数来删除java程序中的目录/文件夹。import java.io.File;/*** 此实用程序类可用于在java递归删除文件夹* @author maxsu*/pub...
  • java 递归 冒泡 6程序

    2010-09-02 17:12:55
    递归 冒泡 长整型加法 空心菱形 空心方形 用java 写的一些常用而且 基础的东西。 如果有人想跟我探讨长整型乘法 和 空心菱形 最简单代码 本人都有方法
  • Java递归算法

    2020-12-22 17:40:01
    Java递归算法是基于Java语言实现的递归算法。  递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解。  ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,767
精华内容 1,506
关键字:

java递归程序

java 订阅