【数据结构与算法】第六章:栈与递归

简介: 栈有一个重要应用是在程序设计语言中实现递归,它通常把一个大型复杂问题的描述和求解变得简洁和清晰。因此递归算法常常比非递归算法更易设计,尤其是当问题本身或所涉及的数据结构是递归定义的时候,使用递归方法更加合适。本节将介绍栈在递归算法的内部实现中所起的作用。

🙊🙊作者主页:🔗求不脱发的博客

📔📔 精选专栏:🔗数据结构与算法

📋📋 精彩摘要:栈有一个重要应用是在程序设计语言中实现递归,它通常把一个大型复杂问题的描述和求解变得简洁和清晰。因此递归算法常常比非递归算法更易设计,尤其是当问题本身或所涉及的数据结构是递归定义的时候,使用递归方法更加合适。本节将介绍栈在递归算法的内部实现中所起的作用。

💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞


📚目录

📖【数据结构与算法】第六章:栈与递归及队列的表示与实现

📝1️⃣采用递归算法解决的问题

📝2️⃣递归过程与递归工作栈

📝3️⃣递归算法的效率分析

📝4️⃣利用栈将递归转换为非递归的方


📖【数据结构与算法】第六章:栈与递归


📝1️⃣采用递归算法解决的问题

所谓递归是指,若在一个函数、过程或者数据结构定义的内部又直接(或间接)出现定义本身的应用,则称它们是递归的,或者是递归定义的。在以下三种情况下,常常使用递归的方法。

✨递归定义的数学函数

image.gif编辑

有很多数学函数是递归定义的。

采取“分治法”进行递归求解的问题需要满足以下三个条件。

    1. 能将一个问题转变成一个新问题,而新问题与原问题的解法相同或类同,不同的仅是处理的对象,并且这些处理对象更小且变化有规律。
    2. 可以通过上述转化而使问题简化。
    3. 必须有一个明确的递归出口,或称递归的边界。

    “分治法”求解递归问题算法的一般形式为:

    void p(参数表)
    {
        if(递归结束条件成立)
            可直接求解; //递归终止的条件
        else p(较小的参数); //递归步骤
    }

    image.gif

    可见,上述阶乘函数和Fibonacci数列的递归过程均与此一般形式相对应。

    ✨具有递归特性的数据结构

    image.gif编辑

    某些数据结构本身具有递归的特性,则它们的操作可递归地描述。

    对于递归的数据结构,相应算法采用递归的方法来实现特别方便。链表的创建和链表结点的遍历输出都可以采用递归的方法。下面通过一个简单的递归算法进行举例介绍。

    遍历输出链表中各个结点的递归算法

    此算法是从前向后遍历输出链表结点的递归算法,调用此递归函数前,参数p指向单链表的首元结点,在递归过程中,p不断指向后继结点,直到p为NULL时递归结束。

    显然,这个问题满足上述给出的采用“分治法”进行递归求解的问题需要满足的三个条件。

    【算法步骤】:

      1. 如果p为NULL,递归结束返回。
      2. 否则输出p->data,p指向后继结点继续递归。

      【算法描述】:

      void TraverseList(LinkList p)
      {
          if(p==NULL)
              return; //递归终止
          else
              cout<data<next); //p指向后继指点继续递归
      }

      image.gif

      在递归算法中,如果当递归结束条件成立,只执行return操作时,“分治法”求解递归问题算法的一般形式可以简化为:

      void p(参数表)
      {
          if(递归结束条件不成立)
          p(较小的参数);
      }

      image.gif

      因此,上述算法可以简化为:

      void TraverseList(LinkList p)
      {
          if(p)
          {
              cout<data<next);
          }
      }

      image.gif

      后面章节要介绍的广义表、二叉树等也是典型的具有递归特性的数据结构,其相应算法也可采用递归的方法来实现。

      ✨问题的解法是递归的

      还有一类问题,虽然问题本身没有明显的递归结构,但用递归求解比迭代求解更简单。

      例如:汉诺塔问题,迷宫问题等等,这里不再详细介绍。


      📝2️⃣递归过程与递归工作栈

      一个递归函数,在函数的执行过程中,需多次进行自我调用。

      与汇编语言程序设计中主程序和子程序之间的链接及信息交换相类似,在高级语言编制的程序中,调用函数和被调用函数之间的链接及信息交换需通过栈来进行。

      通常,当在一个函数的运行期间调用另一个函数时,在运行被调用函数之前,系统需先完成3件事:

        1. 将所有的实参、返回地址等信息传递给被调用函数保存;
        2. 为被调用函数的局部变量分配存储区;
        3. 将控制转移到被调函数的入口。

        而从被调用函数返回调用函数之前,系统也应完成3件工作:

          1. 保存被调函数的计算结果;
          2. 释放被调函数的数据区;
          3. 依照被调函数保存的返回地址将控制转移到调用函数。

          当有多个函数构成嵌套调用时,按照“后调用先返回”的原则。

          image.gif编辑

          image.gif编辑

          【图片来源于:https://blog.csdn.net/weixin_40139164/article/details/108964924】

          上述函数之间的信息传递和控制转移必须通过“栈”来实现,即系统将整个程序运行时所需的数据空间安排在一个栈中,每当调用一个函数时,就为它在栈顶分配一个存储区,每当从一个函数退出时,就释放它的存储区,则当前正运行的函数的数据区必在栈顶。

          一个递归函数的运行过程类似于多个函数的嵌套调用,只是调用函数和被调用函数是同一个函数,因此,和每次调用相关的一个重要概念是递归函数运行的“层次”。

          假设调用该递归函数的主函数为第0层,则从主函数调用递归函数为进入第1层;从第i层递归调用本函数为进入“下一层”,即第i + 1层。反之,退出第i层递归应返回至“上一层”,即第i − 1层。

          为了保证递归函数正确执行,系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个工作记录,其中包括所有的实参、所有的局部变量,以及上一层的返回地址。每进入一层递归,就产生一个新的工作记录压入栈顶。每退出一层递归,就从栈顶弹出一个工作记录,则当前执行层的工作记录必是递归工作栈栈顶的工作记录,称这个记录为“活动记录”。

          下面阶乘函数Fact(4)为例,介绍递归过程中递归工作栈和活动记录的使用。

          主函数调用Fact(4),当函数运行结束后,控制返回到RetLoc1,在此处n被赋为24(即4!)

          void main( )
          {
              long n;            //调用Fact (4)时记录进栈
              n=Fact(4);        //返回地址RetLoc1在赋值语句
              RetLoc1
          }

          image.gif

          为说明方便起见,将阶乘函数算法改写为:

          //为说明方便起见,将阶乘函数算法改写为:
          long Fact(long n )
          {    
              long temp;
              if (n==0) return 1;        //活动记录退栈
              else temp=n*Fact(n-1);        //活动记录进栈
              //返回地址RetLoc2在计算语句
              RetLoc2
              return temp;                //活动记录退栈
          }

          image.gif

          这里暂忽略局部变量temp的入栈和出栈情况。RetLoc2是递归调用Fact (n-1)的返回地址,当Fact(n-1)结束后,返回到RetLoc2,在此处计算n*(n-1)!,然后将结果赋给临时变量temp。

          image.gif编辑

          主函数执行后依次启动了5个函数调用。主程序外部调用Fact(4)的活动记录在栈底,Fact (1)调用Fact (0)进栈的活动记录在栈顶。

          递归结束条件出现于函数Fact(0)的内部,执行Fact(0)引起了返回语句的执行。退出栈顶的活动记录,返回地址返回到上一层Fact(1)的调用递归处RetLoc2,继续执行语句temp=1*1,接着执行return temp又引起新的退栈操作。此退栈过程直至Fact(4)执行完毕后,将控制权转移给main为止。


          📝3️⃣递归算法的效率分析

          ✨时间复杂度分析

          在算法分析中,当一个算法中包含递归调用时,其时间复杂度的分析可以转化为一个递归方程求解。实际上,这个问题是数学上求解渐近阶的问题,而递归方程的形式多种多样,其求解方法也不一而足。迭代法是求解递归方程的一种常用方法,其基本步骤是迭代地展开递归方程的右端,使之成为一个非递归的和式,然后通过对和式的估计来达到对方程左端(即方程的解)的估计。

          下面以阶乘的递归函数Fact(n)为例,说明通过迭代法求解递归方程来计算时间复杂度的方法。

          设Fact(n)的执行时间是T(n)。此递归函数中语句if(n==0) return 1;的执行时间是O(1),递归调用Fact(n-1)的执行时间是T(n-1),所以else return n*Fact(n-1);的执行时间是O(1)+ T(n-1)。

          其中,设两数相乘和赋值操作的执行时间为O(1),则对某常数C、D有如下递归 方程:

          设n>2,利用上式对T(n-1)展开,即在上式中用n-1代替n得到

          T(n-1)=C+T(n-2)

          再代入T(n)=C+T(n-1)中,有

          T(n)=2C+T(n-2)

          同理,当n>3时有

          T(n)=3C+T(n-3)

          依次类推,当n>i时有

          T(n) =iC+T(n-i)

          最后,当i=n时有

          T(n)=nC+T(0)=nC+D

          求得递归方程的解为:T(n)=O(n)

          采用这种方法计算Fibonacci数列和Hanoi塔问题递归算法的时间复杂度均为O(2n)。

          ✨空间复杂度分析

          递归函数在执行时,系统需设立一个“递归工作栈”存储每一层递归所需的信息,此工作栈是递归函数执行的辅助空间,因此,分析递归算法的空间复杂度需要分析工作栈的大小。

          对于递归算法,空间复杂度

          S(n) = O(f (n))

          其中,f(n)为“递归工作栈”中工作记录的个数与问题规模n的函数关系。

          根据这种分析方法不难得到,前面讨论的阶乘问题、Fibonacci数列问题、Hanoi塔问题的递归算法的空间复杂度均为O(n)。


          📝4️⃣利用栈将递归转换为非递归的方法

          通过上述讨论,可以看出递归程序在执行时需要系统提供隐式栈这种数据结构来实现,对于一般的递归过程,仿照递归算法执行过程中递归工作栈的状态变化可直接写出相应的非递归算法。这种利用栈消除递归过程的步骤如下。

            1. 设置一个工作栈存放递归工作记录(包括实参、返回地址及局部变量等)。
            2. 进入非递归调用入口(即被调用程序开始处)将调用程序传来的实在参数和返回地址入栈(递归程序不可以作为主程序,因而可认为初始是被某个调用程序调用)。
            3. 进入递归调用入口:当不满足递归结束条件时,逐层递归,将实参、返回地址及局部变量入栈,这一过程可用循环语句来实现—模拟递归分解的过程。
            4. 递归结束条件满足,将到达递归出口的给定常数作为当前的函数值。
            5. 返回处理:在栈不空的情况下,反复退出栈顶记录,根据记录中的返回地址进行题意规定的操作,即逐层计算当前函数值,直至栈空为止—模拟递归求值过程。

            通过以上步骤,可将任何递归算法改写成非递归算法。但改写后的非递归算法和原来比较起来,结构不够清晰,可读性差,有的还需要经过一系列的优化,这里不再举例详述。

            由于递归函数结构清晰,程序易读,而且其正确性容易得到证明,因此,利用允许递归调用的语言(如C语言)进行程序设计时,给用户编制程序和调试程序带来很大方便。因为对这样一类递归问题编程时,不需用户自己而由系统来管理递归工作栈。

            相关文章
            |
            定位技术 Android开发
            uniapp获取wifi连接状态
            uniapp获取wifi连接状态
            1724 0
            |
            网络安全 网络虚拟化 网络架构
            计算机网络实验(华为eNSP模拟器)——第二章 VRP通用路由平台介绍
            计算机网络实验(华为eNSP模拟器)——第二章 VRP通用路由平台介绍
            计算机网络实验(华为eNSP模拟器)——第二章 VRP通用路由平台介绍
            |
            Python
            VSCode运行Python教程
            VSCode运行Python教程
            3469 0
            VSCode运行Python教程
            |
            存储 缓存 JSON
            Unity资源热更新知识梳理及工作流介绍
            研究了大半年的热更,才做出了一套相对完善的热更架构。不得不说,这块的知识点还是多而杂的,值得专门开篇博文来记录梳理。
            3708 0
            |
            7月前
            |
            人工智能 测试技术 调度
            移动端 RPA 的架构重构:基于多模态视觉大模型的自动化调度系统压测复盘
            本文复盘企业级移动端RPA重构实践,介绍如何以“侠客工坊”AI数字员工平台替代传统坐标录制方案:基于多模态大模型实现视觉语义决策、高并发多机型调度、零代码编排、异常自愈及MCP协议集成,显著提升自动化鲁棒性与运维效率。
            539 10
            |
            8月前
            |
            人工智能 安全 API
            无Token限制玩转OpenClaw:Ollama Mac部署+阿里云零基础教程+避坑指南
            2026年,开源AI智能体OpenClaw(曾用名Clawdbot/Moltbot,昵称“龙虾”)凭借“自然语言驱动、全场景执行”的核心优势持续爆红,而本地大模型部署方案的成熟,更是彻底打破了API Token限制的枷锁。此前Windows与Linux平台的Ollama+OpenClaw部署教程广受好评,众多Mac用户纷纷留言索要专属指南。
            2292 10
            |
            API PHP 开发者
            速卖通商品详情接口(速卖通API系列)
            速卖通(AliExpress)是阿里巴巴旗下的跨境电商平台,提供丰富的商品数据。通过速卖通开放平台(AliExpress Open API),开发者可获取商品详情、订单管理等数据。主要功能包括商品搜索、商品详情、订单管理和数据报告。商品详情接口aliexpress.affiliate.productdetail.get用于获取商品标题、价格、图片等详细信息。开发者需注册账号并创建应用以获取App Key和App Secret,使用PHP等语言调用API。该接口支持多种请求参数和返回字段,方便集成到各类电商应用中。
            1108 5
            |
            消息中间件 存储 Kafka
            浅谈现代消息队列与云存储
            讲述消息系统在现代化演进中软硬一体化,百万队列,分级存储等诸多竞争力特性的诞生和落地效果。探讨业界领先的 Shared-Log 存储计算分离,FFM与协程,RDMA 传输,列式存储等技术,将消息向流的领域延伸。
            |
            人工智能 文字识别 自然语言处理
            三分钟搞定图片识别+翻译+地图定位,通义灵码 2.5 真的太猛了
            在本次体验中,我通过通义灵码 2.5 实测其全新集成的 3000+ MCP 工具能力,展示了如何仅凭一句自然语言指令,就能快速完成 OCR、翻译、地图等多个常用服务的调用与组合。通义灵码不仅自动匹配合适工具,还能生成完整调用代码,省去繁琐的 SDK 集成和文档查阅过程,大幅提升开发效率。这次升级让 AI 编程助手真正具备了“工具理解 + 代码落地”的能力,是开发流程的一次深度革新。
            1128 7
            |
            人工智能 前端开发 关系型数据库
            过年啦,做一个春节贺卡生成器
            本文介绍了如何获取和利用现有的大模型资源,结合魔笔低代码,低成本、高效率地打造一个 AI 春节贺卡生成器。
            916 38