java新人基础入门之递归调用

一、递归概念

递归本质:程序调用自身的编程技巧叫做递归。

程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调;

用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过;

程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

二、递归的三个条件:

  • 边界条件
  • 递归前进段
  • 递归返回段

当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

下面通过两个示例程序来说明:

使用Java代码求5的阶乘。(5的阶乘=5*4*3*2*1)

package org.wxp.recursion; 

/**
 * 计算5的阶乘(result = 5*4*3*2*1)
 * @author Champion.Wong
 *
 *
 */
public class Test01 {
 public static void main(String[] args) {
  System.out.println(f(5));
 } 

 public static int f(int n) {
  if (1 == n)
   return 1;
  else
   return n*f(n-1);
 }
} 

此题中,按照递归的三个条件来分析:

(1)边界条件:阶乘,乘到最后一个数,即1的时候,返回1,程序执行到底;

(2)递归前进段:当前的参数不等于1的时候,继续调用自身;

(3)递归返回段:从最大的数开始乘,如果当前参数是5,那么就是5*4,即5*(5-1),即n*(n-1)

使用Java代码求数列:1,1,2,3,5,8......第40位的数

package org.wxp.recursion; 

/**
 * 求数列:1,1,2,3,5,8......第40位的数
 * @author Champion.Wong
 *
 */
public class Test_02_Fibonacci {
 public static void main(String[] args) {
  System.out.println(f(6));
 } 

 public static int f(int n ) {
  if (1== n || 2 == n)
   return 1;
  else
   return f(n-1) + f(n-2);
 }
} 

此题的突破口在:从第3位数开始,本位数是前两位数的和。要计算第多少位的值,那么就需要将位数作为参数传进方法进行计算。

(1)首先,当位数为1和2时,当前返回的值应该是1;

(2)然后,当位数为3时,返回值应该=2=1+1;

当位数为4时,返回值=3=2+1;

当位数为5时,返回值=5=3+2;

当位数为6时,返回值=8=5+3;

......

(3)由(2)得知,大于等于3的情况下,当前位数(n)的数值=f(n-1)+f(n-2)

三、非递归方法实现(迭代方法)

迭代本质:利用变量的原值推算出变量的一个新值,迭代就是A不停的调用B.

通过观察推导,找到解决问题的方法,发现其中的规律,将其转化成程序语言表达出来。

本质:使用合适的数据类型变量代替问题中的数据,将解决问题的方法转化为符合程序语言的逻辑。

public class Fab{

   public static void main( String[] args){

  System.out.println(f(20));
}   

  public static long f(int index){

    if(index == 1 || index == 2){
       return 1;
    }

    long f1 = 1L;
    long f2 = 1L;
    long f = 0;

    for(int i=0; i<index; i++){
       f = f1 + f2;
       f1 = f2;
       f2 = f;
    }
    return f;
  }

}

递归其实是方便了程序员难为了机器,递归可以通过数学公式很方便的转换为程序。其优点就是易理解,容易编程。但递归是用栈机制实现的,每深入一层,都要占去一块栈数据区域,对嵌套层数深的一些算法,递归会力不从心,空间上会以内存崩溃而告终,而且递归也带来了大量的函数调用,这也有许多额外的时间开销。所以在深度大时,它的时空性就不好了。(会占用大量的内存空间)

而迭代虽然效率高,运行时间只因循环次数增加而增加,没什么额外开销,空间上也没有什么增加,但缺点就是不容易理解,编写复杂问题时困难。

能不用递归就不用递归,递归都可以用迭代来代替。(要辩证的看待这个问题,深度不大,还是可以采用递归的)。

总结

到此这篇关于java新人基础入门之递归调用的文章就介绍到这了,更多相关java递归调用内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java 递归深入理解

    一.递归函数,通俗的说就是函数本身自己调用自己... 如:n!=n(n-1)! 你定义函数f(n)=nf(n-1) 而f(n-1)又是这个定义的函数..这就是递归 二.为什么要用递归:递归的目的是简化程序设计,使程序易读 三.递归的弊端:虽然非递归函数效率高,但较难编程,可读性较差.递归函数的缺点是增加了系统开销,也就是说,每递归一次,栈内存就多占用一截 四.递归的条件:需有完成任务的语句,需满足递归的要求(减小而不是发散) 五.递归进阶: 1.用递归算n的阶乘: 分析:n!=n*(n-1)*(

  • Java递归算法经典实例(经典兔子问题)

    题目:古典问题:3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 分析:首先我们要明白题目的意思指的是每个月的兔子总对数:假设将兔子分为小中大三种,兔子从出生后三个月后每个月就会生出一对兔子, 那么我们假定第一个月的兔子为小兔子,第二个月为中兔子,第三个月之后就为大兔子,那么第一个月分别有1.0.0,第二个月分别为0.1.0, 第三个月分别为1.0.1,第四个月分别为,1.1.1,第五个月分别为2.1.2,第六个月分别为3.2.3,第

  • java利用递归调用实现树形菜单的样式

    一:需求 现有以需求就是把某一个帖子的全部评论展示出来. 二:分析 关于对帖子的评论分为主评论和子评论,主评论就是对帖子的直接评论,子评论就是对评论的评论. 三:思路 先获取某一个帖子的全部主评论,递归判断是否有子评论,获取子评论. 递归本质:程序调用自身的编程技巧叫做递归. 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调 用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模

  • java 用递归获取一个目录下的所有文件路径的小例子

    复制代码 代码如下: private List<String> ergodic(File file,List<String> resultFileName){        File[] files = file.listFiles();        if(files==null)return resultFileName;// 判断目录下是不是空的        for (File f : files) {            if(f.isDirectory()){// 判

  • Java递归遍历树形结构

    废话不多说了,直接给大家贴代码,具体代码如下所示: //菜单树形结构 public JSONArray treeMenuList(JSONArray menuList, int parentId) { JSONArray childMenu = new JSONArray(); for (Object object : menuList) { JSONObject jsonMenu = JSONObject.fromObject(object); int menuId = jsonMenu.ge

  • Java无限级树(递归)超实用案例

    如下所示: @Override public String getEmployeeBysup(String employeeID) { String str=""; str = getEmployeeBysupSelas(employeeID, str); return str.substring(0, str.lastIndexOf(",")); } @Override public String getEmployeeBysupSelas(String empl

  • 快速排序算法原理及java递归实现

    快速排序 对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序.使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好.就平均时间而言,是目前被认为最好的一种内部排序方法 基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 三个指针: 第一个指针称为pivotkey指针(枢轴),第二个指

  • JAVA实现遍历文件夹下的所有文件(递归调用和非递归调用)

    JAVA 遍历文件夹下的所有文件(递归调用和非递归调用) 1.不使用递归的方法调用. public void traverseFolder1(String path) { int fileNum = 0, folderNum = 0; File file = new File(path); if (file.exists()) { LinkedList<File> list = new LinkedList<File>(); File[] files = file.listFile

  • Java方法递归调用实例解析

    这篇文章主要介绍了Java方法递归调用实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 /* 关于方法的递归调用 1.什么是递归? -方法自身调用自身 a(){ a(){ } } 2.递归是很耗费栈内存的,递归算法可以不用的时候尽量不用 3.一下程序运行的时候发生了这样一个错误[不是异常,是错误Error]: java.lang.StackOverflowErroe 栈内存溢出错误. 错误放生无法挽回,只有一个结果,就是JVM停止工作 4

  • Java递归算法的使用分析

    递归算法是一种直接或者间接地调用自身的算法.在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解. 问题1:一列数的规则如下: 1.1.2.3.5.8.13.21.34 ,求第30位数是多少?使用递归实现 复制代码 代码如下: public class FibonacciSequence {    public static void main(String[] args){        System.out.println(Fribonacci(9))

随机推荐