递归算法讲解(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)等。以二叉树的先序遍历为例,先访问根节点,然后递归地访问左子树和右子树,代码如下:

展开过程

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/481700.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

yolo辅助我们健身锻炼

使用软件辅助健身能够大大提升运动效果并帮助你更轻松地达成健身目标。确保每次锻炼都更加高效且针对性强,精确记录你的训练进度,帮助你更清晰地看到自己的进步,避免无效训练。 借助YOLO11的尖端计算机视觉技术,跟踪和分析锻炼变得异常简单。它可以无缝检测和监控多种锻炼…

YOLO系列论文综述(从YOLOv1到YOLOv11)【第3篇:YOLOv1——YOLO的开山之作】

YOLOv1 1 摘要2 YOLO: You Only Look Once2.1 如何工作2.2 网络架构2.3 训练2.4 优缺点 YOLO系列博文: 【第1篇:概述物体检测算法发展史、YOLO应用领域、评价指标和NMS】【第2篇:YOLO系列论文、代码和主要优缺点汇总】【第3篇:YOL…

基于Java Springboot学生信息管理系统

一、作品包含 源码数据库设计文档全套环境和工具资源部署教程 二、项目技术 前端技术:Html、Css、Js、Vue、Element-ui 数据库:MySQL 后端技术:Java、Spring Boot、MyBatis 三、运行环境 开发工具:IDEA/eclipse 数据库&…

基于Pytorch的CIFAR100数据集上从ResNet50到VGG16的知识蒸馏实验记录

知识蒸馏的概念 可以参照NeurIPS2015的论文“Distilling the Knowledge in a Neural Network”了解知识蒸馏的概念。 知识蒸馏的狭义概念就是从复杂模型中迁移知识来提升简单模型的性能。复杂模型称之为教师模型,简单模型称之为学生模型。最近,笔者重温…

#Java-JDK7、8的时间相关类,包装类

1. JDK7-Date类 我们先来看时间的相关知识点 世界标准时间: 格林尼治时间/格林威治时间(Greenwich Mean Time)简称GMT。目前世界标准时间(UTC)已经替换为:原子钟中国标准时间: 世界标准时间8小时 时间单位换算: 1秒1000毫秒 1毫秒1000微秒 1微秒1000纳秒 Date类 Date类…

glog在vs2022 hello world中使用

准备工作 设置dns为阿里云dns 223.5.5.5,下载cmake,vs2022,git git clone https://github.com/google/glog.git cd glog mkdir build cd build cmake .. 拷贝文件 新建hello world并设置 设置预处理器增加GLOG_USE_GLOG_EXPORT;GLOG_NO_AB…

深度学习:梯度下降法

损失函数 L:衡量单一训练样例的效果。 成本函数 J:用于衡量 w 和 b 的效果。 如何使用梯度下降法来训练或学习训练集上的参数w和b ? 成本函数J是参数w和b的函数,它被定义为平均值; 损失函数L可以衡量你的算法效果&a…

半桥LLC谐振变换器及同步整流MATLAB仿真(二)

在上文《半桥LLC谐振变换器及同步整流MATLAB仿真(一)》讲解了半桥LLC谐振变换器的工作原理,本文将利用MATLAB搭建电路模型进行仿真。 参数:输入电压:400Vdc;输出电压范围:36-50V ;输…

利用若依代码生成器实现课程管理模块开发

目录 前言1. 环境准备1.1 数据库表设计与导入 2. 使用若依代码生成器生成模块代码2.1 导入数据库表2.2 配置生成规则2.2.1 基本信息配置2.2.2 字段信息配置2.2.3 生成信息配置 3. 下载与集成生成代码3.1 解压与集成3.2 启动项目并验证 4. 优化与扩展4.1 前端优化4.2 后端扩展 结…

AI前景分析展望——GPTo1 SoraAI

引言 人工智能(AI)领域的飞速发展已不仅仅局限于学术研究,它已渗透到各个行业,影响着从生产制造到创意产业的方方面面。在这场技术革新的浪潮中,一些领先的AI模型,像Sora和OpenAI的O1,凭借其强大…

springboot359智慧草莓基地管理系统(论文+源码)_kaic

毕 业 设 计(论 文) 题目:智慧草莓基地管理系统 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本智慧草莓基地管理系统就…

排序算法之插入排序篇

插入排序 思路&#xff1a; 就是将没有排序的元素逐步地插入到已经排好序的元素后面&#xff0c;保持元素的有序 视频的实现过程如下&#xff1a; 插入排序全过程 代码实现过程如下&#xff1a; public static void Insertion(int[] arr) { for (int i 1; i < arr.length…

【机器学习】支持向量机SVR、SVC分析简明教程

关于使用SVM进行回归分析的介绍很少&#xff0c;在这里&#xff0c;我们讨论一下SVR的理论知识&#xff0c;并对该方法有一个简明的理解。 1. SVC简单介绍 SVR全称是support vector regression&#xff0c;是SVM&#xff08;支持向量机support vector machine&#xff09;对回…

SpringMVC-08-json

8. Json 8.1. 什么是Json JSON(JavaScript Object Notation, JS 对象标记) 是一种轻量级的数据交换格式&#xff0c;目前使用特别广泛。采用完全独立于编程语言的文本格式来存储和表示数据。简洁和清晰的层次结构使得 JSON 成为理想的数据交换语言。易于人阅读和编写&#xf…

APM32使用I2C驱动OLED

实验效果 本次实验主要讲APM32的I2C外设的初始化和APM32作为主机如何发送数据&#xff0c;OLED的驱动写起来较难本次实验不涉及。由于条件有限本次只能讲主机发送&#xff0c;接收也没有涉及。 硬件原理图 源代码 I2C初始化部分 #ifndef __BSP__IIC_H__ #define __BSP__IIC_…

QT布局详解

ui设计器设计界面很方便&#xff0c;为什么还要手写代码? (1)更好的控制布局 (2)更好的设置qss (3)代码复用 创建水平布局 包含头文件 #include<QHBoxLayout> 创建水平布局QHBoxLayout *pHLay new QHBoxLayout(父窗口指针);//一般填this QPushButton *pBtn1 n…

宏集eXware物联网网关在水务管理系统上的应用

一、前言 水务管理系统涵盖了对城市水网、供水、排水、污水处理等多个环节的监控与管理。随着物联网&#xff08;IoT&#xff09;技术的快速发展&#xff0c;物联网网关逐渐成为水务管理系统中的关键组成部分。 宏集物联网网关以其高效的数据采集、传输和管理功能&#xff0c…

不修改内核镜像的情况下,使用内核模块实现高效监控调度时延

一、背景 在之前的博客 调度时延的观测_csdn 调度时延的观测 杰克崔-CSDN博客 里&#xff0c;我们讲了多种监控调度时延的方法&#xff0c;有依靠系统现有节点来监控&#xff0c;但是依赖系统现有节点做不到每个单词调度时延的监控&#xff0c;也讲了通过修改内核代码&#xf…

在 ASP.NET C# Web API 中实现 Serilog 以增强请求和响应的日志记录

介绍 日志记录是任何 Web 应用程序的关键方面。它有助于调试、性能监控和了解用户交互。在 ASP.NET C# 中&#xff0c;集成 Serilog 作为记录请求和响应&#xff08;包括传入和传出的数据&#xff09;的中间件可以显著提高 Web API 的可观察性和故障排除能力。 在过去的几周里&…

【开源免费】基于Vue和SpringBoot的技术交流分享平台(附论文)

博主说明&#xff1a;本文项目编号 T 053 &#xff0c;文末自助获取源码 \color{red}{T053&#xff0c;文末自助获取源码} T053&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析…