当前位置: 首页 > news >正文

递归方法的理解

递归方法调用 :方法自己调用自己的现象就称为递归。
递归的分类 : 直接递归、间接递归。
 直接递归:方法自身调用自己
public void methodA (){
methodA ();
}

间接递归:可以理解为A()方法调用B()方法,B()方法调用C()方法,C()方法调用A()方法。 

public static void A (){
B ();
}
public static void B (){
C ();
}
public static void C (){
A ();
}
说明
递归方法包含了一种 隐式的循环
递归方法会 重复执行 某段代码,但这种重复执行无须循环控制。
递归一定要向 已知方向 递归,否则这种递归就变成了无穷递归,停不下来,类似于 死循环 。最终
发生 栈内存溢出

举例1:计算1 ~ n的和

public class RecursionDemo {
public static void main ( String [] args ) {
RecursionDemo demo = new RecursionDemo ();
// 计算 1~num 的和,使用递归完成
int num = 5 ;
// 调用求和的方法
int sum = demo . getSum ( num );
// 输出结果
System . out . println ( sum );
}
/*
通过递归算法实现 .
参数列表 :int
返回值类型 : int
*/
public int getSum ( int num ) {
/*
num 1 , 方法返回 1,
相当于是方法的出口 ,num 总有是 1 的情况
*/
if ( num == 1 ){
return 1 ;
}
/*
num 不为 1 , 方法返回 num +(num-1) 的累和
递归调用 getSum 方法
*/
return num + getSum ( num - 1 );
}
}

代码执行图解:

代码解释

/*
* 当程序执行时,它会按照以下流程进行:1. `main` 方法被调用。
2. 一个 `RecursionDemo` 类的对象 `demo` 被创建。
3. `n` 被赋值为 5。
4. 调用 `demo.getSum(n)` 方法,其中 `n` 的值为 5。
5. 进入 `getSum` 方法。
6. `n` 的值不为 1,因此程序执行 `return n + getSum(n - 1);`,其中 `n - 1` 的值为 4。
7. 程序递归调用 `getSum` 方法,将参数值 `4` 传递给它。
8. 再次进入 `getSum` 方法。
9. `n` 的值不为 1,因此程序执行 `return n + getSum(n - 1);`,其中 `n - 1` 的值为 3。
10. 程序递归调用 `getSum` 方法,将参数值 `3` 传递给它。
11. 再次进入 `getSum` 方法。
12. `n` 的值不为 1,因此程序执行 `return n + getSum(n - 1);`,其中 `n - 1` 的值为 2。
13. 程序递归调用 `getSum` 方法,将参数值 `2` 传递给它。
14. 再次进入 `getSum` 方法。
15. `n` 的值不为 1,因此程序执行 `return n + getSum(n - 1);`,其中 `n - 1` 的值为 1。
16. 程序递归调用 `getSum` 方法,将参数值 `1` 传递给它。
17. 再次进入 `getSum` 方法。
18. `n` 的值为 1,因此程序直接返回 1。
19. 回到上一层递归调用,将返回的值 1 加上当前层的 `n` 的值(为 2),得到结果 3,返回给上一层。
20. 继续返回上一层递归调用,将返回的值 3 加上当前层的 `n` 的值(为 3),得到结果 6,返回给上一层。
21. 继续返回上一层递归调用,将返回的值 6 加上当前层的 `n` 的值(为 4),得到结果 10,返回给上一层。
22. 继续返回上一层递归调用,将返回的值 10 加上当前层的 `n` 的值(为 5),得到结果 15,返回给上一层。
23. 回到 `main` 方法,将返回的结果 15 赋值给 `sum` 变量。
24. `System.out.println(sum);` 将结果打印到控制台上。所以,程序的输出结果为 `15`。
*
*
*
* */
}

举例2:递归方法计算n!

public int multiply ( int num ){
if ( num == 1 ){
return 1 ;
} else {
return num * multiply ( num - 1 );
}
}

 

public int f ( int num ){
if ( num == 0 ){
return 1 ;
} else if ( num == 1 ){
return 4 ;
} else {
return 2 * f ( num - 1 ) + f ( num - 2 );
}
}

举例3:已知有一个数列:f(0) = 1f(1) = 4f(n+2)=2*f(n+1) + f(n),其中n是大于0的整数,求f(10)的值。

public int func ( int num ){
if ( num == 20 ){
return 1 ;
} else if ( num == 21 ){
return 4 ;
} else {
return func ( num + 2 ) - 2 * func ( num + 1 );
}
}

举例4:计算斐波那契数列(Fibonacci)的第n个值

斐波那契数列满足如下规律,
1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 ,....
即从第三个数开始,一个数等于前两个数之和。假设 f(n) 代表斐波那契数列的第 n 个值,那么 f(n) 满足:
f(n) = f(n-2) + f(n-1);
// 使用递归的写法
int f ( int n ) { // 计算斐波那契数列第 n 个值是多少
if ( n < 1 ) { // 负数是返回特殊值 1 ,表示不计算负数情况
return 1 ;
}
if ( n == 1 || n == 2 ) {
return 1 ;
}
return f ( n - 2 ) + f ( n - 1 );
}
// 不用递归
int fValue ( int n ) { // 计算斐波那契数列第 n 个值是多少
if ( n < 1 ) { // 负数是返回特殊值 1 ,表示不计算负数情况
return 1 ;
}
if ( n == 1 || n == 2 ) {
return 1 ;
}
// 从第三个数开始, 等于 前两个整数相加
int beforeBefore = 1 ; // 相当于 n=1 时的值
int before = 1 ; // 相当于 n=2 时的值
int current = beforeBefore + before ; // 相当于 n=3 的值
// 再完后
for ( int i = 4 ; i <= n ; i ++ ) {
beforeBefore = before ;
before = current ;
current = beforeBefore + before ;
/* 假设 i=4
beforeBefore = before; // 相当于 n=2 时的值
before = current; // 相当于 n=3 的值
current = beforeBefore + before; // 相当于 n = 4 的值
假设 i=5
beforeBefore = before; // 相当于 n=3 的值
before = current; // 相当于 n = 4 的值
current = beforeBefore + before; // 相当于 n = 5 的值
....
*/
}
return current ;
}

举例5:面试题

宋老师,我今天去百度面试,遇到一个一个双重递归调用的问题,我琢磨了一下,完全不知道为什
么。打断点了,也还是没看懂为什么程序会那样走。您有空可以看一下,求指教。

private int count = 0 ;
public int recursion ( int k ) {
count ++ ;
System . out . println ( "count1:" + count + " k:" + k );
if ( k <= 0 ) {
return 0 ;
}
return recursion ( k - 1 ) + recursion ( k - 2 ); //287
//return recursion(k - 1);//11
//return recursion(k - 1) + recursion(k - 1);//2047
}

剖析:

最后说两句:
1. 递归调用会占用大量的系统堆栈,内存耗用多,在递归调用层次多时速度要比循环 慢的
,所以在使用递归时要慎重。
2. 在要求高性能的情况下尽量避免使用递归,递归调用既花时间又 耗内存 。考虑使用循环迭 代。

相关文章:

递归方法的理解

递归方法调用 &#xff1a;方法自己调用自己的现象就称为递归。 递归的分类 : 直接递归、间接递归。 直接递归&#xff1a;方法自身调用自己 public void methodA (){ methodA (); } 间接递归&#xff1a;可以理解为A()方法调用B()方法&#xff0c;B()方法调用C()方法&am…...

css之flex布局文本不换行不显示省略号的解决方法

文章目录 一、单行长文本显示省略号二、flex布局下的处理技巧 一、单行长文本显示省略号 先讲讲常规情况下长文本不跨行显示省略号的代码&#xff1a; overflow: hidden; //不允许内容超出盒子 white-space: nowrap; //不允许文本跨行 text-overflow: ellipsis; //文本超…...

华清远见STM32U5开发板助力2024嵌入式大赛ST赛道智能可穿戴设备及IOT选题项目开发

第七届&#xff08;2024&#xff09;全国大学生嵌入式芯片与系统设计竞赛&#xff08;以下简称“大赛”&#xff09;已经拉开帷幕&#xff0c;大赛的报名热潮正席卷而来&#xff0c;高校电子电气类相关专业&#xff08;电子、信息、计算机、自动化、电气、仪科等&#xff09;全…...

若依框架实现不同端用户登录(后台管理用户和前台会员登录——sping security多用户)

目录 需求背景 前期准备 实现UserDetailsService接口 改造loginUser 声明自定义AuthenticationManager 的bean 自定义登录接口 参考文章 效果如下 需求背景 用若依搭建的后台管理环境&#xff0c;但是前台用户系统&#xff08;前端&#xff09;并没有和若依的前端集成在一起。…...

【解決|三方工具】Obi Rope 编辑器运行即崩溃问题

开发平台&#xff1a;Unity 2021.3.7 三方工具&#xff1a;Unity资产工具 - Obi Rope   问题背景 使用Unity三方开发工具 - Obi Rope 模拟绳索效果。配置后运行 Unity 出现报错并崩溃。通过崩溃日志反馈得到如下图所示 这是一个序列化问题造成的崩溃&#xff0c;指向性为 Obi…...

岭师大数据技术原理与应用-序章-软工版

HeZaoCha-CSDN博客 序章—软工版 一、环境介绍1. VMware Workstation Pro2. CentOS3. Java4. Hadoop5. HBase6. MySQL7. Hive 二、系统安装1. 虚拟网络编辑器2. 操作系统安装 三、结尾 先说说哥们写这系列博客的原因&#xff0c;本来学完咱也没想着再管部署这部分问题的说&…...

Leetcode 680. 验证回文串 II

给你一个字符串 s&#xff0c;最多 可以从中删除一个字符。 请你判断 s 是否能成为回文字符串&#xff1a;如果能&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;s “aba” 输出&#xff1a;true 示例 2&#xff1a…...

网络安全接入认证-802.1X接入说明

介绍 802.1X是一个网络访问控制协议&#xff0c;它可以通过认证和授权来控制网络访问。它的基本原理是在网络交换机和认证服务器之间建立一个安全的通道&#xff0c;并要求客户端提供身份验证凭据。如果客户端提供的凭据是有效的&#xff0c;交换机将开启端口并允许访问。否则&…...

iPhone的iOS系统:定义移动智能体验,引领科技潮流之巅

来自&#xff1a;dlshuhua.com/post/83721.html 在移动智能设备领域&#xff0c;iPhone一直以其出色的性能和独特的用户体验脱颖而出。而这一切的背后&#xff0c;离不开其强大的操作系统——iOS。iOS系统不仅为iPhone提供了强大的性能支持&#xff0c;更通过不断创新和升级&a…...

计算机网络:传输控制协议(Transmission Control Protocol-TCP协议

计算机网络&#xff1a;传输控制协议&#xff08;Transmission Control Protocol-TCP协议&#xff09; 本文目的前置知识点TCP协议简介主要特性通信流程1. 建立连接的过程(三次握手&#xff0c;243)1.1 为什么要三次握手&#xff0c;两次不行吗&#xff1f; 2. 释放连接的过程(…...

GEE实践应用|热岛效应(一)地表温度计算

目录 1.学习目标 2.理论介绍 3.从MODIS获得地表温度 4.从Landsat卫星获得地表温度 1.学习目标 ①了解如何使用GEE计算地表温度 2.理论介绍 城市化涉及用建筑物、道路和停车场等建筑结构取代自然景观。这种土地覆盖的改变也改变了土地表面的特性。这些变化的范围从表面反射和…...

Java查找算法知识点(含面试大厂题和源码)

查找算法是计算机科学中的基础概念&#xff0c;它们在解决实际问题时扮演着关键角色。了解和掌握不同的查找算法&#xff0c;能够帮助我们更高效地处理数据检索任务。以下是一些关于查找算法的关键知识点&#xff1a; 算法分类&#xff1a; 线性查找算法&#xff1a;按照顺序逐…...

67、yolov8目标检测和旋转目标检测算法部署Atlas 200I DK A2开发板上

基本思想&#xff1a;需求部署yolov8目标检测和旋转目标检测算法部署atlas 200dk 开发板上 一、转换模型 链接: https://pan.baidu.com/s/1hJPX2QvybI4AGgeJKO6QgQ?pwdq2s5 提取码: q2s5 from ultralytics import YOLO# Load a model model YOLO("yolov8s.yaml")…...

A Little Is Enough: Circumventing Defenses For Distributed Learning

联邦学习的攻击方法&#xff1a;LIE 简单的总结&#xff0c;只是为了能快速想起来这个方法。 无目标攻击 例如总共50个客户端&#xff0c;有24个恶意客户端&#xff0c;那么这个时候&#xff0c;他需要拉拢2个良性客户端 计算 50 − 24 − 2 50 − 24 0.923 \frac{50-24-2}{…...

文心一言 VS 讯飞星火 VS chatgpt (225)-- 算法导论16.3 7题

七、推广赫夫曼算法&#xff0c;使之能生成三进制的码字(即码字由符号0、1、2组成)&#xff0c;并证明你的算法能生成最优三进制码。如果要写代码&#xff0c;请用go语言。 文心一言&#xff1a; 推广赫夫曼算法以生成三进制码字需要对算法进行一定的修改&#xff0c;确保在每…...

【计算机】——51单片机——持续更新

单片机是一种内部包含CPU、存储器和输入/输出接口等电路的集成电路&#xff08;IC芯片&#xff09; 单片机是单片微型计算机&#xff08;Single Chip Microcomputer&#xff09;的简称&#xff0c;用于控制领域&#xff0c;所以又称为微型控制器&#xff08;Microcontroller U…...

QT资源添加调用

添加资源文件&#xff0c;新建资源文件夹&#xff0c;命名resource&#xff0c;然后点下一步&#xff0c;点完成 资源&#xff0c;右键add Prefix 添加现有文件 展示的label图片切换 QLabel *led_show; #include "mainwindow.h" #include<QLabel> #include&l…...

LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】

LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】 题目描述&#xff1a;解题思路一&#xff1a;哈希表和排序&#xff0c;这里最关键的点是&#xff0c;乱序单词的排序结果必然是一样的&#xff08;从而构成哈希表的key&#xff09;。解题思路二&#xff1a;解题思路三…...

绘制特征曲线-ROC(Machine Learning 研习十七)

接收者操作特征曲线&#xff08;ROC&#xff09;是二元分类器的另一个常用工具。它与精确度/召回率曲线非常相似&#xff0c;但 ROC 曲线不是绘制精确度与召回率的关系曲线&#xff0c;而是绘制真阳性率&#xff08;召回率的另一个名称&#xff09;与假阳性率&#xff08;FPR&a…...

.Net 知识杂记

记录平日中琐碎的.net 知识点。不定期更新 目标框架名称(TFM) 我们创建C#应用程序时&#xff0c;在项目的工程文件(*.csproj)中都有targetFramework标签&#xff0c;以表示项目使用的目标框架 各种版本的TFM .NET Framework .NET Standard .NET5 及更高版本 UMP等 参考文档&a…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...