Java递归详解_java难不难学

Java递归详解_java难不难学学习目标:提示:这里可以添加学习目标例如:一周掌握Java入门知识学习内容:提示:这里可以添加要学的内容例如:1、搭建Java开发环境2、掌握Java基本语法3、掌握条件语句4、掌握循环语句学习时间:提示:这里可以添加计划学习的时间例如:1、周一至周五晚上7点—晚上9点2、周六上午9点-上午11点3、周日下午3点-下午6点学习产出:提示:这里统计学习计划的总量例如:1、技术笔记2遍2、CSDN技术博客3篇

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Java递归详解


前言

递归是一种非常重要的算法思想,无论你是前端开发,还是后端开发,都需要掌握它。在日常工作中,统计文件夹大小,解析xml文件等等,都需要用到递归算法。它太基础太重要了,这也是为什么面试的时候,面试官经常让我们手写递归算法。本文呢,将跟大家一起学习递归算法~

什么是递归?

递归,在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。简单来说,递归表现为函数调用函数本身。

递归最恰当的比喻,就是查词典。我们使用的词典,本身就是递归,为了解释一个词,需要使用更多的词。当你查一个词,发现这个词的解释中某个词仍然不懂,于是你开始查这第二个词,可惜,第二个词里仍然有不懂的词,于是查第三个词,这样查下去,直到有一个词的解释是你完全能看懂的,那么递归走到了尽头,然后你开始后退,逐个明白之前查过的每一个词,最终,你明白了最开始那个词的意思。

看一个递归的代码例子吧,如下:

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

递归的特点

实际上,递归有两个显著的特征,终止条件和自身调用:

终止条件:递归必须有一个终止的条件,即不能无限循环地调用本身。

自身调用:原问题可以分解为子问题,子问题和原问题的求解方法是一致的,即都是调用自身的同一个函数。
在这里插入图片描述

递归应用场景

哪些问题我们可以考虑使用递归来解决呢?即递归的应用场景一般有哪些呢?

  • 阶乘问题
  • 二叉树深度
  • 汉诺塔问题
  • 斐波那契数列
  • 快速排序、归并排序(分治算法体现递归)
  • 遍历文件,解析xml文件

递归解题思路

解决递归问题一般就三步曲,分别是:

第一步,定义函数功能
第二步,寻找递归终止条件
第二步,递推函数的等价关系式
这个递归解题三板斧理解起来有点抽象,我们就用阶乘(factorial)来举个例子吧

1.定义函数功能

定义函数功能,就是说,你这个函数是干嘛的,做什么事情,换句话说,你要知道递归原问题是什么呀?比如你需要解决阶乘问题,定义的函数功能就是n的阶乘,如下:

//n的阶乘(n为大于0的自然数)
int factorial (int n){ 
   

}

2.寻找递归终止条件

递归的一个典型特征就是必须有一个终止的条件,即不能无限循环地调用本身。所以,用递归思路去解决问题的时候,就需要寻找递归终止条件是什么。比如阶乘问题,当n=1的时候,不用再往下递归了,可以跳出循环啦,n=1就可以作为递归的终止条件,如下:

//n的阶乘(n为大于0的自然数)
int factorial (int n){ 
   
    if(n==1){ 
   
      return 1;
    }
}

3.递推函数的等价关系式

递归的「本义」,就是原问题可以拆为同类且更容易解决的子问题,即「原问题和子问题都可以用同一个函数关系表示。递推函数的等价关系式,这个步骤就等价于寻找原问题与子问题的关系,如何用一个公式把这个函数表达清楚」。阶乘的公式就可以表示为 f(n) = n * f(n-1), 因此,阶乘的递归程序代码就可以写成这样,如下:

int factorial (int n){ 
   
    if(n==1){ 
   
      return 1;
    }
    return n * factorial(n-1);
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/192052.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Mybatis分页插件使用的详解[通俗易懂]

    Mybatis分页插件使用的详解[通俗易懂]前言关于分页,一般来说rowBounds这种假分页都上不了台面,我们往往都选哟真分页,那么还不想搞得很麻烦,Mybatis的分页插件就为后端程序员解决了这个问题例子首先需要导入依赖,没错pagehelper<dependency><groupId>com.github.pagehelper</groupId><artifactId>pagehelper</artifactId><v

  • Ubuntu 10.04 更新源[通俗易懂]

    Ubuntu 10.04 更新源[通俗易懂]1.sudogedit/etc/apt/sources.list编辑你的源列表,将原来的内容全部删除,当然之前也可以用sudocp/etc/apt/sources.list/etc/apt

  • BatchMD5Modify_4F-MDMB-BUTINACA

    BatchMD5Modify_4F-MDMB-BUTINACA写前bb最早是看了matlab的代码,搭了环境,demo也跑了,就再也没碰过了。之后想自己把测试和训练部分全部跑通,找了个用pytorch写的代码,看的过程中发现自己还是很多细节部分不是很清楚。虽然文章写的很一笔带过,但是看着代码会发现还是很多疑问的。代码地址:gayhub代码的requirements:UbuntuPython2.7(useAnaconda2.*here)…

  • 详解 傅里叶变换的物理意义

    详解 傅里叶变换的物理意义这是一篇辅助理解傅里叶变换的博客,下面如果有不适合或错误的表达,请大家在评论区给我留言,我一定积极修改。一、傅里叶分析关于任意函数的傅里叶变换频域(频率,振幅、相位三维正交)图像,韩同学给出一个形象的解释,这里借用韩同学的图片准确表达一下,一个函数的傅里叶级数展开如下式,二、傅里叶变换在了解了时域与频域的空间特征后,那我们再来看下傅里叶变换,这里可以看潘工的文章,潘工有趣的引入了:简单→分解→正交→内积思想,并提出函数之间内积(投影)的定义,,其中g表示共轭。e^ix本质上是一个单位圆,则原

    2022年10月25日
  • 纯HTML+CSS网页设计期末作业(个人网站)

    目录纯HTML+CSS网页设计期末作业(个人网站)效果展示源码index.htmlindex.cssabout.htmlhobbies.htmlhobbies.cssme.htmlme.cssbook1.htmlbook.csssongci.htmlsongci.css缺陷纯HTML+CSS网页设计期末作业(个人网站)效果展示index页面about页面hobbies页面书籍介绍页面元曲介绍页面源码index.html<!DOCTYPEhtml><h

  • mnist有多少张图片(怎么读取图片文字)

    importosfromPILimportImageimportnumpyasnp#读取文件夹mnist下的42000张图片,图片为灰度图,所以为1通道,如果是将彩色图作为输入,则将1替换为3,图像大小28*28defload_data(): data=np.empty((42000,1,28,28),dtype="float32") label=np.em…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号