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

本篇文章为大家展示了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. 代码解析

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

#includeusing 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#includeusing 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 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++显式栈如何实现递归，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注行业资讯频道。