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)
blank

相关推荐

  • 数据结构与算法经典书籍——大话数据结构(带配套源码)

    数据结构与算法经典书籍——大话数据结构(带配套源码)书本下载链接:链接:https://pan.baidu.com/s/1jgVnbBZoLgA8pshpxbapOQ密码:577l配套程序链接:https://pan.baidu.com/s/1HYka42KngWT2el7T0HO7LA密码:i6hw虽说数据结构以美国人MarkAllenWeiss写的《数据结构与算法分析——C语言实现》最好,但是我发现他的书让人很不容易理解,可能我们…

  • Typescript教程_安装typescript

    Typescript教程_安装typescript前言由于最近在使用vue3写项目,使用vue3的前提就是要学习TypeScript,TypeScript算是JavaScript的升级版,TypeScript包含JavaScript和自己的一些特性

  • latex 不换行

    latex 不换行1.网上找了很久都是教怎么换行,为了不让一些类似Fig.number换行,可以用\mbox{Fig.number}命令。

  • sigaction信号处理

    sigaction信号处理1.sigactionintsigaction(intsignum,conststructsigaction*act,structsigaction*oldact);signum:可以指定SIGKILL和SIGSTOP以外的所有信号2.structsigactionstructsigaction{void(*sa_handler)(int);

  • git安装教程图文详解_git vim命令

    git安装教程图文详解_git vim命令奥力给一、通过Yum源安装#1.卸载旧版本yumremovegit#2.安装yum源的Git版本yuminstall-ygit#3.查看版本gitversion#输出gitversion1.8.3.1#4.查看本文下方的「三、配置全局环境变量」二、通过编译安装#如果没有安装wget则安装yuminstall-ywget2.1下载点击查看最新版本#我这里操作时最新版本为V2.35.1,以下命.

    2022年10月22日
  • pycharm激活码最新【在线注册码/序列号/破解码】

    pycharm激活码最新【在线注册码/序列号/破解码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

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

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