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

递归算法讲解(c基础)

  1. 递归的定义
    • 递归是指在函数的定义中使用函数自身的方法。它是一种解决问题的策略,将一个大型复杂的问题逐步分解为规模更小的、与原问题相似的子问题来解决。当子问题的规模足够小,达到一个可以直接求解的基本情况(也称为终止条件)时,递归过程就停止。
  2. 递归的组成部分
    • 递归调用:函数在其内部调用自身的操作。例如,计算阶乘的函数factorial(n)中,return n * factorial(n - 1)这一行就是递归调用。它表示为了计算n的阶乘,需要先计算n - 1的阶乘,以此类推。
    • 终止条件:这是递归的关键部分,用于停止递归调用,避免无限循环。以阶乘函数为例,当n == 0n == 1时,factorial(n)直接返回1,这就是终止条件。因为0的阶乘和1的阶乘定义为1,此时不需要再进行递归调用。
  3. 递归的执行过程(以阶乘函数为例)
    • 假设我们要计算5的阶乘,即factorial(5)
    • 首先,进入factorial函数,因为n = 5不满足终止条件(n!=0n!=1),所以执行return n * factorial(n - 1),此时需要计算factorial(4)
    • 对于factorial(4),同样不满足终止条件,继续执行return n * factorial(n - 1),需要计算factorial(3)
    • 这个过程一直持续,直到计算factorial(1)。当n = 1时,满足终止条件,factorial(1)直接返回1
    • 然后,递归调用开始返回。factorial(2)得到2*1 = 2(因为factorial(2)执行2*factorial(1)),factorial(3)得到3*2 = 6(因为factorial(3)执行3*factorial(2)),以此类推,最终factorial(5)得到5*4*3*2*1 = 120
  4. 递归的优点
    • 代码简洁:对于一些具有重复结构的问题,如树的遍历、斐波那契数列的计算等,递归可以使代码非常简洁。例如,计算斐波那契数列的函数:

展开过程

这段代码通过递归很直观地表达了斐波那契数列的定义:第n项等于第n - 1项和第n - 2项之和。

  • 易于理解(对于某些问题):当问题本身具有递归性质时,递归算法可以自然地反映问题的结构。例如,在树结构中,递归遍历(如先序遍历、中序遍历、后序遍历)就很好地利用了树的递归定义:树是由根节点、左子树和右子树组成的,左子树和右子树本身也是树。

  1. 递归的缺点
    • 效率问题:递归函数可能会导致大量的函数调用开销。以斐波那契数列的递归计算为例,在计算fibonacci(n)时,会重复计算很多子问题。例如,计算fibonacci(5)时,fibonacci(3)会被计算两次,随着n的增大,重复计算的次数会呈指数增长,导致时间复杂度较高(斐波那契数列的递归计算时间复杂度为)。
    • 可能导致栈溢出:由于递归是通过函数调用栈来实现的,每次递归调用都会在栈中占用一定的空间。如果递归深度太深(例如,一个无限递归或者递归深度超过了栈的容量),就会导致栈溢出错误。例如,在一个栈空间有限的环境中,计算一个非常大的阶乘或者深度很深的树的遍历可能会出现这种情况。
  2. 递归的应用场景
    • 树和图的遍历:如二叉树的先序、中序、后序遍历,图的深度优先搜索(DFS)等。以二叉树的先序遍历为例,先访问根节点,然后递归地访问左子树和右子树,代码如下:

展开过程

  • 数学计算:如阶乘、斐波那契数列等计算。
  • 分治算法:将一个大问题分解为多个小的子问题,分别解决子问题后再合并结果。例如,快速排序算法中的划分操作部分递归地对左右子数组进行排序,这也是一种分治思想的体现。

相关文章:

递归算法讲解(c基础)

递归的定义 递归是指在函数的定义中使用函数自身的方法。它是一种解决问题的策略,将一个大型复杂的问题逐步分解为规模更小的、与原问题相似的子问题来解决。当子问题的规模足够小,达到一个可以直接求解的基本情况(也称为终止条件&#xff09…...

AJAX一、axios使用,url组成(协议,域名,资源路径)查询参数和化简,错误处理,请求/响应报文,状态码,接口文档,

一、AJAX是什么 概念 &#xff1a; AJAX是一种与服务器&#xff08;后端&#xff09;通信的技术 二、请求库axios的基本用法 1导包 2使用 // 1. 发请求 axios({ url: 请求地址 }).then(res > { // 2.接收并使用数据 }) <body><p class"province"…...

QT6学习第六天 初识QML

QT6学习第六天 创建Qt Quick UI项目使用Qt Quick DesignerQML 语法基础导入语句 import对象 object 和属性 property布局注释表达式和属性绑定QML 编码约定 设置应用程序图标 创建Qt Quick UI项目 如果你有只测试QML相关内容快速显示界面的需求&#xff0c;这时可以创建Qt Qui…...

映射vim键位,基本功能键位表(未更完)

键位映射&#xff1a;建议使用jj代替esc,毕竟esc离手那么远 linux下修改方法是&#xff1a;vim /etc/vim/vimrc 在该文件尾添加inoremap jj <Esc>该方法可以同样可以用到其他键位映射上 i&#xff1a;表示这个映射是在插入模式&#xff08;insert mode&#xff09;下有效…...

Python学习笔记(5)Python的创建型设计模式

创建型设计模式&#xff08;Creational Design Patterns&#xff09;&#xff0c;主要关注对象的创建机制。这类模式可以使得系统更加独立于如何创建、组合和表示其对象。通过将这些职责分离出来&#xff0c;创建型设计模式有助于提高代码的灵活性和复用性。 本书的范例代码已经…...

qt QAnimationDriver详解

1、概述 QAnimationDriver是Qt框架中提供的一个类&#xff0c;它主要用于自定义动画帧的时间控制和更新。通过继承和实现QAnimationDriver&#xff0c;开发者可以精确控制动画的时间步长和更新逻辑&#xff0c;从而实现丰富和灵活的动画效果。QAnimationDriver与QAbstractAnim…...

零拷贝相关知识点(一)

前言 大家好&#xff0c;我是程序员田螺。 零拷贝是老生常谈的问题啦&#xff0c;大厂非常喜欢问。比如Kafka为什么快&#xff0c;RocketMQ为什么快等&#xff0c;都涉及到零拷贝知识点。最近技术讨论群几个伙伴分享了阿里、虾皮的面试真题&#xff0c;也都涉及到零拷贝。因此…...

STM32的CAN波特率计算

公式&#xff1a; CAN波特率 APB总线频率 / &#xff08;BRP分频器 1&#xff09;/ (SWJ BS1 BS2) SWJ一般为1。 例如STM32F407的&#xff0c;CAN1和CAN2都在在APB1下&#xff0c;频率是42000000 如果想配置成1M波特率&#xff0c;则计算公式为&#xff1a;...

简单好用的折线图绘制!

折线图的概念及作用&#xff1a; 折线图&#xff08;Line Chart&#xff09;是一种常见的图表类型&#xff0c;用于展示数据的变化趋势或时间序列数据。它通过一系列的数据点&#xff08;通常表示为坐标系中的点&#xff09;与这些点之间的线段相连&#xff0c;直观地展示变量…...

Hadoop批量计算实验

参考: Hadoop(一)之实验一CentOS7配置Hadoop系统:配置CentOS和下载安装包_基于虚拟机cents7搭建hadoop实验目的-CSDN博客 --------------------------------------------------------- 一、安装Vmware 二、创建虚拟机 1.安装centos7 ①打开VMware,点击新建虚拟机。 …...

基于rpcapd与wireshark的远程实时抓包的方法

基于rpcapd与wireshark的远程实时抓包的方法 服务端安装wireshark侧设置 嵌入式设备或服务器上没有图形界面&#xff0c;通常使用tcpdump抓包保存为pcap文件后&#xff0c;导出到本地使用wireshark打开分析&#xff0c;rpcapd可与wireshark配合提供一种远程实时抓包的方案&…...

ubuntu多版本安装gcc

1.ubuntu安装gcc 9.3.1 $ sudo apt update $ sudo apt install gcc-9 g-9 二、配置GCC版本 安装完成后&#xff0c;需要使用update-alternatives命令来配置GCC版本。这个命令允许系统在多个安装的版本之间进行选择 1.添加GCC 9.3.1到update-alternatives管理 $ sudo update-a…...

算法刷题Day1

BM47 寻找第k大 第一天就随便记录吧&#xff0c;万事开头难&#xff0c;我好不容易开的头&#xff0c;就别难为自己&#xff0c;去追求高质量了。嘿嘿嘿 题目 传送门 解题思路一&#xff1a;维护一个大小为k的最小堆。最后返回堆顶元素。 代码&#xff1a; # # 代码中的类名…...

泛化调用 :在没有接口的情况下进行RPC调用

什么是泛化调用&#xff1f; 在RPC调用的过程中&#xff0c;调用端向服务端发起请求&#xff0c;首先要通过动态代理&#xff0c;动态代理可以屏蔽RPC处理流程&#xff0c;使得发起远程调用就像调用本地一样。 RPC调用本质&#xff1a;调用端向服务端发送一条请求消息&#x…...

Java 泛型详细解析

泛型的定义 泛型类的定义 下面定义了一个泛型类 Pair&#xff0c;它有一个泛型参数 T。 public class Pair<T> {private T start;private T end; }实际使用的时候就可以给这个 T 指定任何实际的类型&#xff0c;比如下面所示&#xff0c;就指定了实际类型为 LocalDate…...

题解:CF332B Maximum Absurdity

CF332B CF332B 暴力思路 题目要我们找两个不重叠的区间&#xff0c;并使区间的值最大。那我们可以考虑使用双重循环搭配前缀和暴力求最大值。代码如下。 for(int i1;i<n;i) {ll lsum[ik-1]-sum[i-1],maxx;for(int jik;j<n;j){maxxlsum[jk-1]-sum[j-1];if(maxx>ans.…...

Vue 集成和使用 SQLite 的完整指东

1. 引言 SQLite 是一种轻量级的关系型数据库管理系统&#xff0c;以其简单易用、无需服务器等特点广泛应用于嵌入式系统、移动应用和小型应用程序中。在 Web 开发中&#xff0c;尤其是前端应用开发中&#xff0c;SQLite 可以作为客户端本地存储的一种选择&#xff0c;为用户提…...

【JVM什么时候触发YoungGC和FullGC】

YoungGC 年轻代Eden区满&#xff0c;就会触发YoungGC FullGC 老年代空间不足 经过多次GC后的大年龄对象会被放进老年代&#xff0c;或创建的大对象会直接在老年代分配&#xff0c;此时若老年代空间不足&#xff0c;就会触发FullGC。空间分配担保失败 触发YoungGC的时候会进行…...

ubuntu配置网络

1&#xff0c;设置桥接模式 1-1&#xff1a; 确定。 1-2&#xff1a; 编辑--->虚拟网络编辑器 刚安装ubuntu的时候&#xff0c;可能没有任何VMnet. 更改设置的目的&#xff1a; 添加VMnet0&#xff0c;并且设置VMnet为桥接模式--自动桥接。 如果没有VMnet0,选择添加网络…...

第十一课 Unity编辑器创建的资源优化_预制体和材质篇(Prefabs和Materials)详解

预制体(Prefabs) Unity中的预制体是用来存储游戏对象、子对象及其所需组件的可重用资源&#xff0c;一般来说预制体资源可充当资源模版&#xff0c;在此模版基础上可以在场景中创建新的预制体实例。 使用预制体的好处 由于预制体系统可以自动保持所有实例副本同步&#xff0c…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

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

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

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...