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

递归-需要满足三个条件

一,概述

递归是一种应用非常广泛的算法(或者编程技巧)。很多数据结构和算法的编码实现都要用到递归,比如 DFS 深度优先搜索、前中后序二叉树遍历等。

去的过程叫“递”,回来的过程叫“归”。基本上所有的递归问题都可以用递推公式来表示。

递归需要满足的三个条件

  1. 一个问题的解可以分解为几个子问题的解;
  2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样;
  3. 存在递归终止条件。

二,常见的递归问题

  • 斐波那契数列:递推公式:f(n) = f(n-1) + f(n-2)
  • 跳台阶问题:递推公式:f(n) = f(n-1) + f(n-2)

斐波那契数列问题的”记忆化递归“实现代码如下:

// 1,直接递归会超出时间限制,需要使用记忆化递归
int fib(int n) {if (n == 0) return 0;if (n == 1 || n == 2) return 1;if (vec[n] != -1) return vec[n];vec[n] = (fib(n - 1) + fib(n - 2)) % mod;return vec[n];
}

二,如何编写递归代码

递归问题的层层调用分析是不符合人类直觉的,因此没必要用人脑去分解递归代码的每个步骤,正确的做法是,遇到递归问题就拆分问题并抽象成递归公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。

三,递归代码要警惕堆栈溢出

递归代码涉及到函数调用,函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完成返回时,才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险。

通过在代码中限制递归调用的最大深度的方式一定程度上可以解决堆栈溢出的问题。伪代码如下:


// 全局变量,表示递归的深度。
int depth = 0;int f(int n) {++depth;if (depth > 1000) throw exception;if (n == 1) return 1;return f(n-1) + 1;
}

但这种做法并不能完全解决问题,因为最大允许的递归深度跟当前线程剩余的栈空间大小有关,事先无法计算。如果实时计算,代码过于复杂,就会影响代码的可读性。所以,如果最大深度比较小,比如 10、50,就可以用这种方法,否则这种方法并不是很实用。

四,递归代码要警惕重复计算

为了避免重复计算,我们可以通过一个数据结构(比如散列表)来保存已经求解过的 f(k)f(k)f(k)。当递归调用到 f(k)f(k)f(k) 时,先看下是否已经求解过了。如果是,则直接从散列表中取值返回,不需要重复计算。

这种”递归+备忘录(记忆化递归)“的方法相比简单的递归,可以减少时间复杂度,本质是用空间换时间。

五,总结

递归是一种非常高效、简洁的编码技巧。只要是满足“三个条件”的问题就可以通过递归代码来解决。

但是递归代码也比较难写、难理解。编写递归代码的关键就是不要把自己绕进去,正确姿势是写出递推公式,找出终止条件,然后再翻译成递归代码。

递归代码虽然简洁高效,但是,递归代码也有很多弊端。比如,堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等,所以,在编写递归代码的时候,一定要控制好这些副作用。

参考资料

《数据结构与算法之美》-递归

相关文章:

递归-需要满足三个条件

一,概述 递归是一种应用非常广泛的算法(或者编程技巧)。很多数据结构和算法的编码实现都要用到递归,比如 DFS 深度优先搜索、前中后序二叉树遍历等。 去的过程叫“递”,回来的过程叫“归”。基本上所有的递归问题都可…...

【剑指Offer-Java】两个栈实现队列

题目 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 输入: [“CQueue”,“appendT…...

Allegro如何将Waived掉的DRC显示或隐藏操作指导

Allegro如何将Waived掉的DRC显示或隐藏操作指导 在用Allegro做PCB设计的时候,如果遇到正常的DRC,可以用Waive的命令将DRC不显示,如下图 当DRC被Waive掉的时候,如何将DRC再次显示出来。类似下图效果 具体操作如下 点击Display...

MATLAB——数据及其运算

MATLAB数值数据数值数据类型的分类1.整型整型数据是不带小数的数,有带符号整数和无符号整数之分。表中列出了各种整型数据的取值范围和对应的转换函数。2.浮点型浮点型数据有单精度(single)和双精度((double)之分&…...

【微信小程序】-- 页面导航 -- 声明式导航(二十二)

💌 所属专栏:【微信小程序开发教程】 😀 作  者:我是夜阑的狗🐶 🚀 个人简介:一个正在努力学技术的CV工程师,专注基础和实战分享 ,欢迎咨询! &…...

gdb查看汇编代码的例子

gdb查看汇编代码的例子 操作步骤 用 gdb 启动可执行文件:gdb executable_file在 gdb 中设置断点:break function_name 或者 break *memory_address运行程序:run当程序停止在断点处时,使用 disassemble 命令来查看汇编代码&#…...

第四讲:如何将本地代码与服务器代码保持实时同步

一、前言 在我们进行 Ambari 二次开发时,通常会先在服务器上部署一套可以使用的 Ambari 环境。 二次开发,就肯定是要改动代码的,我们不能老是在服务器上用vim编辑文件,那样效率太低,始终不是长久之计。 所以我们需要在本地打开我们的Ambari源码项目,比如用idea工具,可…...

cuda调试(一)vs2019-windows-Nsight system--nvtx使用,添加nvToolsExt.h文件

cuda调试 由于在编程过程中发现不同的网格块的结构,对最后的代码结果有影响,所以想记录一下解决办法。 CUDA的Context、Stream、Warp、SM、SP、Kernel、Block、Grid cuda context (上下文) context类似于CPU进程上下,表示由管理层 Drive …...

向Spring容器中注入bean有哪几种方式?

文章前言: 写这篇文章的时候,我正在手机上看腾讯课堂的公开课,有讲到 Spring IOC 创建bean有哪几种方式,视频中有提到过 set注入、构造器注入、注解方式注入等等;于是,就想到了写一篇《Spring注入bean有几种…...

如何用 Python采集 <豆某yin片>并作词云图分析 ?

嗨害大家好鸭!我是小熊猫~ 总有那么一句银幕台词能打动人心 总有那么一幕名导名作念念不忘 不知道大家有多久没有放松一下了呢? 本次就来给大家采集一下某瓣电影并做词云分析 康康哪一部才是大家心中的经典呢? 最近又有哪一部可能会成为…...

Python装饰器的具体实用示例

示例1:普通装饰器 def name(n):def func(x):res n(xx)return resreturn funcname def run(x): # run name(run)print(x)if __name__ __main__:run(1) # 2def name(n):def func(*x):res n(xx)return resreturn funcname def run(x): # run name(run)pr…...

谈谈我对Retrofit源码的理解

文章目录一、Retrofit简介二、使用介绍2.1 app / build.gradle添加依赖2.2 创建 Retrofit 实例2.3 创建 API 接口定义文件2.4 使用 Retrofit 进行网络请求三、源码分析3.1 创建 Retrofit 实例: 建造者模式创建Retrofit3.2 实例化API接口: 动态代理模式3.3 获取Observable返回值…...

八股文(三)

目录 一、 如何理解原型与原型链 二、 js继承 三、 vuex的使用 1.mutation和action的区别 mutation action 2.Vuex都有哪些API 四、 前端性能优化方法 五、 类型判断 题目 (1)typeof判断哪个类型会出错(即结果不准确)&…...

2023最新实施工程师面试题

1、两电脑都在同一个网络环境中,A 电脑访问不到 B 电脑的共享文件。此现象可能是哪些 方面所导致?怎样处理? 答:首先你要确定是不是在一个工作组内,只有在一个工作组内才可以共享文件,然后看一个看一看有没有防火墙之类的,然后确定文件是不是已经共享 2、 电脑开机时风扇…...

安卓逆向_6 --- JNI 和 NDK

Java 本机接口规范内容:https://docs.oracle.com/en/java/javase/19/docs/specs/jni/index.html JNI官方中文资料:https://blog.csdn.net/yishifu/article/details/52180448 NDK 官方文档:https://developer.android.google.cn/training/ar…...

Pod控制器

K8S之控制器详解#简介#在kubernetes中,按照Pod的创建方式可以将其分为两类:自主式:kubernetes直接创建出来的Pod,这种Pod删除后就没有了,也不会重建。控制器创建pod:通过Pod控制器创建的Pod,这种Pod删除之后还会自动重…...

微服务到云原生

微服务到云原生 微服务 微服务架构(Microservice Architecture)是一种架构概念,旨在通过将功能分解到各个离散的服务中以实现对解决方案的解耦。 微服务是一种架构风格,一个大型复杂软件应用由一个或多个微服务组成。系统中的各…...

Spring Security 实现自定义登录和认证(1):使用自定义的用户进行认证

1 SpringSecurity 1.1 导入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId> </dependency>1.2 编写配置类 在spring最新版中禁用了WebSecurityConfigurerAdapter…...

Spring Cloud(微服务)学习篇(七)

Spring Cloud(微服务)学习篇(七) 1.使用代码的方式实现流量限制规则 1.1 变更SentinelController类 1.1.1 加入的代码 //流控限制 (一个或多个资源限流), postConstruct注解的作用是保证项目一启动就会加载,// 一个rule就是一个规则PostConstructpublic void FlowRule(){Li…...

嵌入式安防监控项目——前期知识复习

目录 一、概述 二、C语言 三、数据结构 四、IO进程 五、网络 六、ARM体系结构和接口技术 七、系统移植 八、内核驱动 一、概述 我再报班之前学过51和32&#xff0c;不过都是自学的。报班开始先从应用层入手的&#xff0c;C语言和数据结构。只要是个IT专业的大学这都是必…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...