c++显式栈实现递归介绍

c++显式栈实现递归介绍

目录

前言

1.递归

2.显式栈实现的思路

3.代码解析

前言

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

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 //调用函数B if (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++显式栈实现递归介绍的文章就介绍到这了,更多相关c++递归内容请搜索易知道(ezd.cc)以前的文章或继续浏览下面的相关文章希望大家以后多多支持易知道(ezd.cc)!

推荐阅读

    excel怎么用乘法函数

    excel怎么用乘法函数,乘法,函数,哪个,excel乘法函数怎么用?1、首先用鼠标选中要计算的单元格。2、然后选中单元格后点击左上方工具栏的fx公

    无法读取U盘中的数据

    无法读取U盘中的数据,,核心提示:我有一个512MB的U盘,把它插在电脑显示器里面是空的,但右键单击以查看已经使用USB 480mb文件的属性未设置为隐

    excel中乘法函数是什么?

    excel中乘法函数是什么?,乘法,函数,什么,打开表格,在C1单元格中输入“=A1*B1”乘法公式。以此类推到多个单元。1、A1*B1=C1的Excel乘法公式

    标准差excel用什么函数?

    标准差excel用什么函数?,函数,标准,什么,在数据单元格的下方输入l标准差公式函数公式“=STDEVPA(C2:C6)”。按下回车,求出标准公差值。详细

    EXCEL数据透视表怎么用?是干什么的

    EXCEL数据透视表怎么用?是干什么的,透视,干什么,怎么,excel透视表:数据透视表(Pivot Table)是一种交互式的表,可以进行某些计算,如求和与计数等

    通过备份记录获得数据库的增长

    通过备份记录获得数据库的增长,,通常你想知道数据库是否正在增长,以及它增长了多少,可能比较数据库中每个历史时期的大小。 但是我们怎样才