递归算法 数据结构_数据结构中递归的定义

递归算法 数据结构_数据结构中递归的定义一、什么是递归所谓递归,简单点来说,就是一个函数直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。引用知乎大佬的例子:我们可以把”递归

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

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

一、什么是递归

所谓递归,简单点来说,就是一个函数直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

引用知乎大佬的例子:

我们可以把” 递归 “比喻成 “查字典 “,当你查一个词,发现这个词的解释中某个词仍然不懂,于是你开始查这第二个词。

可惜,第二个词里仍然有不懂的词,于是查第三个词,这样查下去,直到有一个词的解释是你完全能看懂的,那么递归走到了尽头,然后你开始后退,逐个明白之前查过的每一个词,最终,你明白了最开始那个词的意思。

我们把查字典理解成一个函数search(){},而“明白了”就是停止条件。

按这个思路,那这个流程就是这样的:

public void search(){
    //如果明白了就停止函数
    if("明白了"){
       return;
    }
    //没明白调用自己继续查
    search();
}

我们举个简单的例子:

要计算阶乘1*2*3*.....*(n-1)*n,代码如下:

public static int mult(int n) {
    //终止条件,当n=1时直接返回1
    if (n == 1){
        return n;
    }
    //计算n*(n-1).....
    return n * mult(n - 1);
}

二、递归和栈的关系

递归的过程就是出入栈的过程

递归的问题实际上都能拆分成出入栈问题,我们可以举上面计算1*2*3*.....*(n-1)*n这个例子来理解一下:

如果n=4,那么过程就是这样:

  1. mult(4)调用了mult(3)
  2. mult(3)调用了mult(2)
  3. mult(2)调用了mult(1)
  4. 到了mult(1)时满足了终止条件,返回结果

用出入栈的思维理解:

  1. 步骤1-3都是一个入栈过程,mult(4)计算得出结果后入栈,然后运行mult(3)得出结果,然后在入栈……以此类推
  2. 当到达n=1的停止条件时递归停止不再入栈,此时栈深度就是4,这也叫递归深度
  3. 满足停止条件后出栈,mult(1)的结果出栈,与mult(2)的结果出栈相乘,再与随后出栈的mult(3)的结果相乘…..以此类推

递归的本质就是栈的出入过程,所以实际上当深度过深,超过了jvm规定允许的栈最大深度的时候,就会出现栈溢出的问题,也就是java里的StackOverflowError

三、递归的使用条件

那么,我们是时候可以使用递归来解决问题呢:

  • 当问题可以拆分为子问题,并且子问题与原问题解决方法相同
  • 有一个明确的程序停止条件

比如之前的文章中提到连续乘除问题就是一个典型的例子。

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

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

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

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

(0)


相关推荐

  • 激活码 clion 2021【2021.10最新】

    (激活码 clion 2021)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlF6EG2ZUBVX-eyJsa…

  • HTTP请求错误400、401、402、403、404、405、406、407、412、414、500、501、502解析

    HTTP请求错误400、401、402、403、404、405、406、407、412、414、500、501、502解析

    2021年10月12日
  • 无法定位序数10于动态链接库crt.dll_无法定位序数3883于动态链接库

    无法定位序数10于动态链接库crt.dll_无法定位序数3883于动态链接库问题阐述:开发环境:VS2008使用RELEASE生成了可执行文件,发如今某些电脑上能够正常执行,但在部分电脑中执行失败提示:无法定位序数8523于动态链接库mfc90.dll在网上查找了一些资料

  • Android入门学习教程PDF免费下载

    Android入门学习教程PDF免费下载场景Android(安卓)是一种以Linux为基础的开放源码操作系统,主要使用于便携设备。2005年由Google收购注资,并拉拢多家制造商组成开放手机联盟开发改良,逐渐扩展到到平板电脑及其他领域上。实现关注公众号:霸道的程序猿回复:Android书籍免费下载。…

  • wait(),notify(),notifyAll()_多线程wait和sleep

    wait(),notify(),notifyAll()_多线程wait和sleep前言在上一篇中,我们介绍了Java中的线程的基本概念,我们了解到线程是有很多种状态的,本章,我们就来聊聊线程中的状态是如何进行控制与切换的。Java中提供了很多种方法对线程的状态进行控制以及线程之间的通信,包括wait、notify、notifyAll、sleep,下面我们就来看一下它们之间有什么区别,以及如何使用这些方法进行线程状态的控制与通信。线程之间的通信在Java中可以用w…

  • 5大优秀黑客必逛技术网站

    5大优秀黑客必逛技术网站5大优秀黑客必逛技术网站HackForums最理想的黑客技术学习技术根据地,也适用于开发人员游戏开发者,程序员,图形设计师以及网络营销人士HackThisSite提供合法而安全的网络安全资源,可以通过·各类挑战题目测试自己的黑客技能EnilZone一个专门面向黑科群体的论坛,其中也涉及科学,编程以及艺术等领域的内容Exploit-DB提供一整套庞大的归档体…

发表回复

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

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