文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

c++显式栈如何实现递归

2023-06-26 04:10

关注

本篇文章为大家展示了c++显式栈如何实现递归,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。

前言

在大学的课上老师有教过,也就是用循环来实现递归,现在自己回顾一下并且做一下记录。

1. 递归

假设有函数A, 和函数B, 函数B是一个递归函数, 函数A调用函数B。
这个递归的过程分为:

函数A调用函数B,函数A将数据传给函数B。此时进入到函数B内部,函数B通过传参拿到函数A传过来的数据。执行本次调用的操作将新的数据作为参数传入函数B(递归过程, 内部再次执行2~3步骤,以此类推)。退出递归结束。

2. 显式栈实现的思路

由上面的过程可以不难看出,递归的过程遵循 后进后出 这样的一个规律。那么就很容易联想到具有同样特征的栈这样一个数据结构。这里给出显式栈实现递归的思路:
假设已经申请了一个stack的容器,

首先将初始数据压栈,这个类似于递归过程中的函数A最开始调用函数B时将数据传入的操作。接下来是循环操作,条件是true,也就是死循环, 这个类似于函数B内部一直递归调用,至于什么时候结束取决于什么时候遇到递归出口;在这个死循环里应该在每次循环时进行一次条件判定,这个条件判定相当于递归函数中决定什么时候返回的条件判定;接下来进到循环内部,首先取栈顶数据出来,这类似函数B内部取到了传参执行 本次的循环的关键操作,处理数据的任务将新的数据压栈,这部分相当于将新的数据作为参数传入函数B如果触发了循环退出条件,则退出循环

3. 代码解析

上面说了具体思路,现在用代码来说明,首先上递归的写法, 用遍历二叉树作为例子。

#include<iostream>using namespace std;class Node{public:int value;Node* left_child;Node* right_child;Node(int data){this->data = data;this->left_child = nullptr;this->right_child = nullptr;}};void B(Node* node){//这个时候已经经历了步骤2, 函数B拿到了数据root// 步骤3,执行本次递归调用的关键操作cout << node->data<< endl; // 步骤4,拿到新的数据root->left_child和root->right_child//调用函数Bif (node->left_child) B(node->left_child);if (node->right_child) B(node->right_child);//步骤5,递归结束}void A(){Node root(10);  //模拟一颗树B(&root); //步骤1,传参}int main(){A();}
以上步骤3和步骤4的顺序不是固定的,他们顺序的不同各自构成了不同的树遍历方法(先序,中序,后序遍历)。接下来是显式栈实现的写法
#include<iostream>#include<stack>using namespace std;class Node{public:int value;Node* left_child;Node* right_child;Node(int data){this->data = data;this->left_child = nullptr;this->right_child = nullptr;}};int main(){Node root(10);  //模拟一颗树stack<Node*> m_stack;m_stack.push(&root); //步骤1,将根节点压栈, 相当于函数A调用函数B时传参while(true){if (m_stack.empty()){break; //这里相当于步骤5,判定循环结束条件, 也可以写到while条件上//为了思路更清晰,所以写在循环里面,也更好跟递归版本进行比较}//步骤2,取栈顶元素Node* current_node = m_stack.top();m_stack.pop();//步骤3,执行本次循环的关键操作cout << current_node->data<< endl;//步骤4, 拿到新的数据并且压栈if (current_node->left_child)m_stack.push(current_node->left_child);if (current_node->right_child)m_stack.push(current_node->right_child);}}
显式栈实现的版本里,有一个细节就是取完栈顶数据之后需要将栈顶的数据出栈,这样才能使用栈是否空来判断递归出口。

上述内容就是c++显式栈如何实现递归,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯