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++递归内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现递归函数的方法

    递归函数通俗来讲就是自己调用自己本身.这样有很大的好处,代码很方便简洁,把复杂的有规律的运算交给计算机去做. 1.首先定义问题.递归函数(recursion)需要设置一个函数,然后再可以循环往复的执行下去. 2.把问题换成公式. 如把阶乘之和定义为f(n)=n*f(n-1).也就是说n*f(n-1)=n*(n-1)*f(n-2)=...=n*(n-1)*(n-2)*...*1 3.用C++公式编写程序 4.再把递归函数累加 5.完整公式如下 6.输入输出检查之后完全正确 总结:以上就是关于C++

  • C++ 中快排的递归和非递归实现

    快排的递归 void quickSort1(int* root,int low,int high) { int pat=root[low]; if(low<high) { int i=low,j=high; while(i<j) { while(i<j&&root[j]>pat) j--; root[i]=root[j]; while(i<j&&root[i]<pat) i++; root[j]=root[i]; } root[i]=pa

  • C++递归算法实例代码

    递归算法,总结起来具有以下几个特点: 特点1  它有一个基本部分,即直接满足条件,输出     特点2  它有一个递归部分,即 通过改变基数(即n),来逐步使得n满足基本部分的条件,从而输出     特点3  在实现的过程中,它采用了分治法的思想:        即将整体分割成部分,并总是从最小的部分(基本部分)开始入手(输出),其背后的原理在于 当整体递归到部分时,会保留整体的信息,部分满足条件输出的结果会被回溯给整体使用,从而使得整体输出结果.     特点4  每一步操作,整体都会将部分当

  • C++利用递归实现走迷宫

    本文实例为大家分享了C++利用递归实现走迷宫的具体代码,供大家参考,具体内容如下 要求: 1.将地图的数组保存在文件中,从文件中读取行列数 2..动态开辟空间保存地图 3..运行结束后再地图上标出具体的走法 说明: 1.文件中第一行分别放置的是地图的行数和列数 2.其中1表示墙,即路不通,0表示路,即通路 3.程序运行结束后用2标记走过的路径 4.当走到"死胡同"时用3标记此路为死路 5.每到一个点,按照 左 上 右 下 的顺序去试探 6.没有处理入口就是"死胡同"

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

    目录 前言 1. 递归 2. 显式栈实现的思路 3. 代码解析 前言 在大学的课上老师有教过,也就是用循环来实现递归,现在自己回顾一下并且做一下记录. 1. 递归 假设有函数A, 和函数B, 函数B是一个递归函数, 函数A调用函数B.这个递归的过程分为: 函数A调用函数B,函数A将数据传给函数B.此时进入到函数B内部,函数B通过传参拿到函数A传过来的数据.执行本次调用的操作将新的数据作为参数传入函数B(递归过程, 内部再次执行2~3步骤,以此类推).退出递归结束. 2. 显式栈实现的思路 由上面

  • Android显式启动与隐式启动Activity的区别介绍

    前段时间立志坚持写博客,但是发现自己的积累的确不多,于是假期泡了泡图书馆,读了一些很有价值的文章.收获颇多,今天的文章分享为主,共同学习. 为什么要写显式启动与隐式启动Activity.这源于自己的一次面试,被Baidu工程师问道,但是后来觉得自己回答的不好,废话少说,进入正题. 如题,Android的Acitivity启动大致有两种方式:显式启动与隐式启动.下面分别介绍: A:显式启动 对于初学者来说,这个最常见,下面用代码来解释什么是显式启动. 复制代码 代码如下: Intent inten

  • Java并发编程之显式锁机制详解

    我们之前介绍过synchronized关键字实现程序的原子性操作,它的内部也是一种加锁和解锁机制,是一种声明式的编程方式,我们只需要对方法或者代码块进行声明,Java内部帮我们在调用方法之前和结束时加锁和解锁.而我们本篇将要介绍的显式锁是一种手动式的实现方式,程序员控制锁的具体实现,虽然现在越来越趋向于使用synchronized直接实现原子操作,但是了解了Lock接口的具体实现机制将有助于我们对synchronized的使用.本文主要涉及以下一些内容: 接口Lock的基本组成成员 可重入锁Re

  • Java 堆内存与栈内存详细介绍

     Java 中的堆和栈 Java把内存划分成两种:一种是栈内存,一种是堆内存. ​ 在函数中定义的一些基本类型的变量和对象的引用变量都是在函数的栈内存中分配.当在一段代码块中定义一个变量时,java就在栈中为这个变量分配内存空间,当超过变量的作用域后,java会自动释放掉为该变量分配的内存空间,该内存空间可以立刻被另作他用. 堆内存用于存放由new创建的对象和数组.在堆中分配的内存,由java虚拟机自动垃圾回收器来管理.在堆中产生了一个数组或者对象后,还可以在栈中定义一个特殊的变量,这个变量的取

  • 详解Oracle隐式游标和显式游标

    详解Oracle隐式游标和显式游标

    游标是什么?就是在内存开辟的一块临时存储空间. 1.Oracle隐式游标 1.1Oracle有常用的哪些隐式游标 1.2 Oracle隐式游标演示 -- 隐式游标 (使用的表为Oracle默认自带的emp表) -- sql%rowcount:影响记录条数 sql%found:是否有满足条件的记录 set serveroutput on; declare v_ename a_emp.ename%type; begin select ename into v_ename from a_emp whe

  • C#特性 匿名类型与隐式类型局部变量使用介绍

    在本篇中我要介绍两个概念,我觉得这两个东西必须一起来介绍,这样才能连贯. C# 2.0里我们已经匿名方法了,现在类型也玩起匿名来了,怪不得大家"举报"的时候都喜欢匿名,为啥?因为匿名被举报人就找不着报复对象了呗,是的,匿名就是把名字隐藏起来,没有名字谁还能找得到你啊. 匿名类型 在C#里有这样一些类型,它是作为临时储存数据的,生命周期只在这个方法内,方法结束了,这个类型的生命周期也没有了.那么这里我们就可以使用一个匿名类型. 复制代码 代码如下: var KeyPair = new {

  • JavaScript显式数据类型转换详解

    基本概念 将值从一种类型转换为另一种类型称为类型转换,类型转换总是返回基本类型值,如字符串.数字和布尔值,不会返回引用类型值. 类型转换分为"显式"和"隐式":"显式"转换发生在静态类型语言的编译阶段,而"隐式"转换则发生在动态类型语言的运行时. 显式类型转换 非字符串到字符串的类型转换 toString() 方法 数字.布尔值.字符串和对象都有 toString() 方法,但 null 和 undefined 没有. 例子:

  • 深入理解Java显式锁的相关知识

    目录 一.显式锁 二.Lock的常用api 三.Lock的标准用法 四.ReentrantLock(可重入锁) 五.ReentrantReadWriteLock(读写锁) 六.Condition 一.显式锁 什么是显式锁? 由自己手动获取锁,然后手动释放的锁. 有了 synchronized(内置锁) 为什么还要 Lock(显示锁)? 使用 synchronized 关键字实现了锁功能的,使用 synchronized 关键字将会隐式地获取锁,但是它将锁的获取和释放固化了,也就是先获取再释放.

  • Java创建对象（显式创建和隐含创建）

    目录 一.显式创建对象 1. 使用 new 关键字创建对象 2. 调用 java.lang.Class 3. 调用对象的 clone() 方法 4. 调用 java.io.ObjectlnputStream 对象的 readObject() 方法 二.隐含创建对象 对象是对类的实例化.对象具有状态和行为,变量用来表明对象的状态,方法表明对象所具有的行为.Java 对象的生命周期包括创建.使用和清除. 一.显式创建对象 对象的显式创建方式有 4 种. 1. 使用 new 关键字创建对象 这是常用的

  • C#数据类型转换(显式转型、隐式转型、强制转型)

    C#数据类型转换(显式转型、隐式转型、强制转型)

    C# 的类型转换有显式转型 和 隐式转型 两种方式. 显式转型:有可能引发异常.精确度丢失及其他问题的转换方式.需要使用手段进行转换操作. 隐式转型:不会改变原有数据精确度.引发异常,不会发生任何问题的转换方式.由系统自动转换. 不同类型的数据进行操作(加减乘除赋值等等),是需要进行 类型转换 后,才能继续操作.所以需要“类型转换”. 隐式转型 隐式转型容易理解,当两种或多种数据类型进行某种操作时,不需要干预,系统会自动进行隐式转换. 如 int i = 66666; long b = i; /

随机推荐