算法妙妙屋-------1.递归的深邃回响:C++ 算法世界的优雅之旅

前言:

递归是一种在算法中广泛应用的思想,其主体思想是通过将复杂的问题分解为更简单的子问题来求解。具体而言,递归通常包括以下几个要素:

  1. 基本情况(Base Case):每个递归算法必须有一个或多个基本情况,用于定义何时停止递归。基本情况是问题的 最小实例 ,直接返回结果,不再进行进一步的递归。

  2. 递归情况(Recursive Case):当问题不是 基本情况 时,递归算法会将问题 拆分成更小的子问题 。算法会调用自身来解决这些子问题,通常会在调用中传递参数以反映问题的简化。

  3. 合并结果(Combining Results):在递归调用返回后,算法 ***会将子问题的结果合并***,以得到原始问题的解。

递归的优势在于其代码通常更简洁且易于理解,尤其是在处理分治问题(如排序、搜索等)时。然而,递归也可能导致栈溢出问题,因为每次调用都会在栈上占用空间,因此在使用时需要考虑调用深度和性能优化。

下面,我们就用习题来给大家做解释吧!

1. 汉诺塔(easy)(非常经典)

题目链接:汉诺塔

在这里插入图片描述
递归函数流程:

  1. 当前问题规模为n=1时,直接将A中的最上⾯盘⼦挪到C中并返回;
  2. 递归将A中最上⾯的n-1个盘⼦挪到B中;
  3. 将A中最上⾯的⼀个盘⼦挪到C中;
  4. 将B中上⾯n-1个盘⼦挪到C中。

解题思路:

  • 先把n-1盘全部移到B上去

  • 再把第n盘移到C上去

  • 再把n-1盘移到C上去

代码如下:

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C,A.size());
    }


    void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int n)
    {
        if(n==1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }

         dfs(A, C, B,n-1);//这一步是为了将除了最大的盘子留下外,其他全部转移到B盘
         C.push_back(A.back());
         A.pop_back();//这一步是为了把最大的盘子转移到C盘
         dfs(B, A, C,n-1);//这一步是进行递归,B盘变成了A盘,A盘变成了B盘,目的是为了将其他盘全部转移到C盘
    }
};

2.合并两个有序链表(easy)

题目链接:合并两个有序链表
题目描述:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

在这里插入图片描述

算法思路:

  1. 递归函数的含义:交给你两个链表的头结点,你帮我把它们合并起来,并且返回合并后的头结点;
  2. 函数体:选择两个头结点中较⼩的结点作为最终合并后的头结点,然后将剩下的链表交给递归函数
    去处理;
  3. 递归出⼝:当某⼀个链表为空的时候,返回另外⼀个链表。

注意注意注意:链表的题⼀定要画图,搞清楚指针的操作!

解题思路:

  • 判断某一个参数是否为空,为空则返回 另一个参数

  • 如果两者都不为空,则 比较l1的元素和l2元素的大小

  • 元素***小的节点留下***,并把 该节点的next另一节点 作为下一轮递归函数的参数

  • 下一轮递归函数的 返回值变为该节点的next

  • 返回该节点 (小的那一个)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
         if(list1==NULL)
         {
            return list2;
         }

         if(list2==NULL)
          {
            return list1;
          }

        if(list1->val<=list2->val)
        {
            list1->next=mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next=mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

3. 反转链表(easy)

题目链接:反转链表

题⽬描述:

在这里插入图片描述

解题思路:

  • 先通过一层循环找到尾,因为 尾就是新的头节点
  • 找到尾之后,把 head 做为参数,传给递归函数

递归函数:

  • 如果head->next为空,直接返回head

  • 否则,将head->next作为参数进入下一次递归
  • ***下一次递归函数的返回值-***>next=head;
  • head->next=nullptr;
  • 返回head
class Solution {
public:

     ListNode* reverseL(ListNode* head)
     {
       if(head->next==nullptr)
        return head;
     
       else
       { 
        reverseL(head->next)->next=head;
        head->next=nullptr;
        return head;
       }
     }


    ListNode* reverseList(ListNode* head) {
        ListNode* it=head;
        if(head==nullptr)
        return head;
        while(it->next!=nullptr)
        {
            it=it->next;
        }
        reverseL(head);
        return it;
    }
};

4.两两交换链表中的节点(medium)

题目链接:两两交换链表中的节点
题目描述:
在这里插入图片描述

解题思路:

  • 如果(1)head为空,返回nullptr
  • 如果(2)head->next==nullptr,返回head
  • 否则(3)将head->next->next作为参数进行下一次递归
  • 递归的返回值赋值给head->next->next
  • 交换head和head->next
  • 返回原来的head->next
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {


         if(head==nullptr)
        {
            return nullptr;
        }

         else if(head->next==nullptr)
        {
            return head;
        }

         
            head->next->next=swapPairs(head->next->next);
            
            ListNode* it=head->next;
            head->next=head->next->next;
            it->next=head;//交换head和head->next

            return it;
    }
};

结语

解决递归问题时,可以遵循以下经验:

  1. 明确基本情况:确保清楚地定义基本情况,以便在满足条件时能够正确终止递归。

  2. 分解问题:将问题有效地拆分为更小的子问题,确保每次递归调用都朝着基本情况逼近。

  3. 参数管理:仔细选择和管理递归调用中的参数,以便有效传递必要的信息并简化问题。

  4. 结果合并:清晰地规划如何合并子问题的结果,以构建最终解。

  5. 避免重复计算:对于具有重叠子问题的情况(如斐波那契数列),考虑使用记忆化或动态规划来优化性能。

  6. 可视化:在思考递归逻辑时,可以尝试绘制递归树,帮助理解调用过程和结果合并。

  7. 测试和验证:使用边界条件和基本情况测试递归实现,确保其正确性和稳定性。

通过遵循这些经验,可以更有效地解决递归问题,并提高代码的清晰性和可维护性。

好啦,递归问题就讲到这里,下一次讲解的是二叉树的深度搜索,我们下次再见

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

禾川HCQ1控制器程序编译报错如何解决

1、第一次打开用户程序 2、提示库未安装 3、安装库文件 4、脉冲轴库未安装 5、没有错误 去禾川自动化官网,把可以安装的包和库都安装下,程序编译就没有错误了。 6、下载相关包文件

HarmonyOS:@Watch装饰器:状态变量更改通知

Watch应用于对状态变量的监听。如果开发者需要关注某个状态变量的值是否改变&#xff0c;可以使用Watch为状态变量设置回调函数。 说明 从API version 9开始&#xff0c;该装饰器支持在ArkTS卡片中使用。 从API version 11开始&#xff0c;该装饰器支持在元服务中使用。 一、概…

Windows如何查看自己网卡的MAC地址?

本章教程&#xff0c;主要介绍如何在Windows查看自己的网卡mac地址。 一、查询MAC地址方法 打开使用PowerShell&#xff0c;运行以下命令即可查询到自己的网卡MAC地址。 Get-NetAdapter | Select-Object Name, MacAddress二、MAC地址是什么 MAC地址&#xff08;Media Access Co…

Unknown at rule @tailwindscss(unknownAtRules)

一、前言 整合 tailwindcss 后&#xff0c;发现指令提示警告 Unknown at rule tailwindscss(unknownAtRules)&#xff0c;其实是 vscode 无法识别 tailwindscss 指令&#xff0c;不影响使用&#xff0c;但是对于我这种有编程洁癖的人来说&#xff0c;有点膈应。 二、解决方案…

Python 实现深度学习模型预测控制--预测模型构建

链接&#xff1a;深度学习模型预测控制 &#xff08;如果认为有用&#xff0c;动动小手为我点亮github小星星哦&#xff09;&#xff0c;持续更新中…… 链接&#xff1a;WangXiaoMingo/TensorDL-MPC: DL-MPC(deep learning model predictive control) is a software toolkit…

安宝特案例 | AR技术在院外心脏骤停急救中的革命性应用

00 案例背景 在院外心脏骤停 (OHCA) 的突发救援中&#xff0c;时间与效率直接决定着患者的生命。传统急救模式下&#xff0c;急救人员常通过视频或电话与医院医生进行沟通&#xff0c;以描述患者状况并依照指令行动。然而&#xff0c;这种信息传递方式往往因信息不完整或传递延…

书生大模型第一关Linux基础知识

任务一&#xff1a;完成SSH连接与端口映射并运行hello_world.py 1.SSH及其端口映射 2.在VSCode中安装插件&#xff1a; 3.创建开发机 最后点击创建&#xff0c;然后可能需要等待一段较长的时间&#xff0c;大概需要5分钟左右&#xff0c;如果需要排队则更长时间 然后选择…

openGauss数据库-头歌实验1-5 修改数据库

一、查看表结构与修改表名 &#xff08;一&#xff09;任务描述 本关任务&#xff1a;修改表名&#xff0c;并能顺利查询到修改后表的结构。 &#xff08;二&#xff09;相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a; 1.如何查看表的结构&#xff1b; 2.如…

【机器学习】26. 聚类评估方法

聚类评估方法 1. Unsupervised Measure1.1. Method 1: measure cohesion and separationSilhouette coefficient Method 2&#xff1a;Correlation between two similarity matricesMethod 3&#xff1a;Visual Inspection of similarity matrix 2. Supervised measures3. 决定…

基于stm32单片机的智能循迹小车

功能描述 STM32单片机循迹避障蓝牙控制温度采集烟雾采集火焰探测声光报警按键调节OLED显示 1. STM32单片机为控制核心 2. 通过ds18b20传感器测量环境温度 3. 通过mq-2烟雾传感器测量环境中的烟雾浓度 4. 温度阈值和烟雾浓度阈值可以通过按键进行调节 5. 当温度或者烟雾浓度超过…

【图解版】力扣第70题:爬楼梯

推理出状态表达式 f(5)表示到达第5层&#xff0c;所有可能的方法数。 到达第5层&#xff0c;有可能是从第4层走一步上来&#xff0c;也有可能是从第3层走两步上来。所以我们可以慢慢延伸&#xff0c;画出上面&#x1f446;&#x1f3fb;的图。 从图中&#xff0c;我们可以看到…

MySQL基础(三)

目录 一. 插入内容insert 1.1 默认插入 1.2 指定某些列插入数据 1.3 一次插入多行 1.4 insert 插入时间 二. 查询数据select&#xff08;比较复杂&#xff09; 2.1 全列查询 2.2 指定列查询 2.3 查询字段为表达式 2.4 别名 as 2.5 去重查询 distinct 2.6 排序…

OpenAI 的 Whisper:盛名之下,其实难副?

OpenAI 的 Whisper&#xff1a;盛名之下&#xff0c;其实难副&#xff1f; Whisper 的崛起与承诺 严重缺陷的曝光 风险分析 应对措施 结论 在人工智能的浪潮中&#xff0c;OpenAI 一直以其创新性和强大的技术实力备受瞩目。然而&#xff0c;最近 OpenAI 的语音转写工具 Wh…

在kanzi 3.9.8里使用API创建自定义材质

1. kanzi studio设置 1.1 创建一个纹理贴图&#xff0c;起名Render Target Texture 1.2 创建一个Image节点&#xff0c;使用该贴图 2. 代码设置 2.1 创建一个自定义节点类 class mynode2d : public Node2D { public: virtual void renderOverride(Renderer3D& renderer…

音频中sample rate是什么意思?

‌sample rate‌在数字信号处理中&#xff0c;指的是‌采样频率‌&#xff0c;即每秒钟从连续信号中抽取的样本数量。采样频率越高&#xff0c;信号的还原度越高&#xff0c;但同时也会增加计算负担和存储需求‌。 实际应用场景 在音频处理中&#xff0c;设置合适的采样率可以…

杨辉三角形

大家好&#xff0c;今天给大家分享一下杨辉三角形是如何打印的&#xff0c;首先我们来看看它的原理。 我们先来看结果 1.如果把它看为一个二维数组&#xff08;包括后面的空格&#xff09;&#xff0c;那么它数字的这边是一个直角三角形&#xff0c;它的第一列和对角线都为1&a…

详解ARM64可执行程序的生成过程

版权归作者所有&#xff0c;如有转发&#xff0c;请注明文章出处&#xff1a;https://cyrus-studio.github.io/blog/ ARM64可执行程序的生成过程 根据 ARM64 可执行程序生成的四个主要步骤&#xff1a;预处理、编译、汇编、链接&#xff0c;我们可以详细分解整个过程如下 1. …

DB-GPT系列(二):DB-GPT部署(镜像一键部署、源码部署)

一、简介 DB-GPT 是一个开源项目&#xff0c;其将大语言模型 LLM 与数据库紧密结合。该项目主要致力于探索如何让预训练的大规模语言模型&#xff08;例如 GPT&#xff09;能够直接与数据库进行交互&#xff0c;从而生成更为准确且信息丰富的回答。 DB-GPT部署后能否直接使用…

升序数组两两不相等

题目&#xff1a;给定一个排好升序的数组A[1],A[2],… A[n]&#xff0c;其元素的值两两都不相等。请设计一个高效算法&#xff0c;找出其中所有A[]i的下标&#xff0c;并分析其复杂度。 算法分析&#xff1a;一个升序且值都不相等的数组&#xff0c;如果第一个数大于右下标&…

基于vue框架的的乐守护儿童成长记录系统b65tg(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。

系统程序文件列表 项目功能&#xff1a;用户,成长指标,疫苗接种,学业档案,课外活动,旅游经历,交流论坛 开题报告内容 基于Vue框架的乐守护儿童成长记录系统开题报告 一、研究背景与意义 随着科技的飞速发展和家庭对子女成长关注度的不断提升&#xff0c;如何科学、系统地记…