java递归函数

图标

豆瓜

豆瓜网

豆瓜网专栏

首发
豆瓜 图标 2020-06-26 09:38:09

Java学习:递归

递归的思想

以此类推是递归的基本思想。

具体来讲就是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件,这样就不会产生无限递归的情况了。

递归的两个条件

  1. 可以通过递归调用来缩小问题规模,且新问题与原问题有着相同的形式。(自身调用)

  2. 存在一种简单情境,可以使递归在简单情境下退出。(递归出口)

递归三要素:

  1. 一定有一种可以退出程序的情况;

  2. 总是在尝试将一个问题化简到更小的规模

  3. 父问题与子问题不能有重叠的部分

递归:自已(方法)调用自已

例子:用递归把目录下所有的目录及文件全部显示出来

 

复制代码

public class B {    public static void main(String[] args) {
        File file = new File("f:\\123");
        listAllFile(file);
    }    public static void listAllFile(File file) {
        File[] strs = file.listFiles();        for (int i = 0; i < strs.length; i++) {            // 判断strs[i]是不是目录
            if (strs[i].isDirectory()) {
                listAllFile(strs[i]);//递归调用自己
                System.out.println("目录="+strs[i].getName());
            } else {
                System.out.println("文件名="+strs[i].getName());
            }
        }    
    }
}

复制代码

递归算法的一般形式:

复制代码

func( mode){    if(endCondition){      //递归出口          end;
    }else{
         func(mode_small)  //调用本身,递归    }
}

复制代码

例子

求一个数的阶乘是练习简单而典型的例子,阶乘的递推公式为:factorial(n)=n*factorial(n-1),其中n为非负整数,且0!=1,1!=1

我们根据递推公式可以轻松的写出其递归函数:

复制代码

public static long factorial(int n) throws Exception {    if (n < 0)        throw new Exception("参数不能为负!");    else if (n == 1 || n == 0)        return 1;    else
        return n * factorial(n - 1);
}

复制代码

递归的过程

在求解6的阶乘时,递归过程如下所示。

clip_image001

我们会惊奇的发现这个过程和栈的工作原理一致对,递归调用就是通过栈这种数据结构完成的。整个过程实际上就是一个栈的入栈和出栈问题。然而我们并不需要关心这个栈的实现,这个过程是由系统来完成的。

那么递归中的“递”就是入栈,递进;“归”就是出栈,回归。

我们可以通过一个更简单的程序来模拟递进和回归的过程:

 

复制代码

/*
 关于 递归中 递进和回归的理解*/public static void recursion_display(int n) {    int temp=n;//保证前后打印的值一样
     System.out.println("递进:" + temp);    if (n > 0) {
        recursion_display(--n);
    }
    System.out.println("回归:" + temp);
}

复制代码

递归的例子

斐波那契数列

斐波那契数列的递推公式:Fib(n)=Fib(n-1)+Fib(n-2),指的是如下所示的数列:

1、1、2、3、5、8、13、21.....

按照其递推公式写出的递归函数如下:

复制代码

public static int fib(int n) throws Exception {    if (n < 0)        throw new Exception("参数不能为负!");    else if (n == 0 || n == 1)        return n;    else
        return fib(n - 1) + fib(n - 2);
}

复制代码

 递归调用的过程像树一样,通过观察会发现有很多重复的调用。

 

image

归并排序

归并排序也是递归的典型应用,其思想:将序列分为若干有序序列(开始为单个记录),两个相邻有序的序列合并成一个有序的序列,以此类推,直到整个序列有序。

复制代码

//递归过程是:在递进的过程中拆分数组,在回归的过程合并数组public static void mergeSort(int[] source, int[] temp, int first, int last) {    if (first < last) {        int mid = (first + last) / 2;
        mergeSort(source, temp, first, mid);    //归并排序前半个子序列
        mergeSort(source, temp, mid + 1, last); //归并排序后半个子序列
        merge(source, temp, first, mid, last);    //在回归过程中合并
    } else if (first == last) {                    //待排序列只有一个,递归结束
        temp[first] = source[first];
    }
}

复制代码

同样调用过程向树一样,但是它并没有重复调用的问题。在递进的过程中拆分数组,在回归的过程合并数组 。通过递归来实现归并排序,程序结构和条理非常清晰。

clip_image002



本文由豆瓜网专栏作家 豆瓜 投稿发布,并经过豆瓜网编辑审核。

转载此文章须经作者同意,并附上出处(豆瓜网)及本页链接。

若稿件文字、图片、视频等内容侵犯了您的权益,请联系本站进行 投诉处理

相关搜索

java递归函数
图标 图标

豆瓜

豆瓜网

豆瓜网专栏

  • java递归函数

    图标
    豆瓜 图标 · 今天 09:38:09 · 8浏览
  • 不能信任一个安装所需的压缩文件
  • kindeditor上传图片编辑器

    图标
    豆瓜 图标 · 今天 09:33:09 · 8浏览
  • 全部评论

    豆瓜

    豆瓜网

    豆瓜网专栏

  • java递归函数
  • 不能信任一个安装所需的压缩文件
  • kindeditor上传图片编辑器
  • oracle通配符大全
  • tokenstream源码分析
  • 我来说两句