当前位置: 首页 > 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…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...