当前位置:   article > 正文

栈、递归、循环的关系_出栈入栈为什么比循环快

出栈入栈为什么比循环快

==> 学习汇总(持续更新)
==> 从零搭建后端基础设施系列(一)-- 背景介绍


栈和递归其实原理都是差不多的,栈是先进后出,递归也是先进后出,递归也是利用堆栈来实现的,循环可以模拟代替栈和递归,只是用循环太复杂。

首先说明一下栈和堆的不同(这里的栈是系统自动维护的一种数据结构,内存分配方式和我们自己写的栈数据结构是不一样的。)。

栈:就是那些由编译器在需要的时候分配,在不需要的时候自动清除的变量的存储区。里面的变量通常是局部变量、函数参数等。在一个进程中,位于用户虚拟地址空间顶部的是用户栈,编译器用它来实现函数的调用。
递归的就是用系统栈来实现的,一般栈的大小默认为1MB,所以有时候使用递归的时候会出现栈溢出。这时候你可以修改栈的默认大小。如下图:

大小是以字节为单位的,最小是4个字节。

堆:就是那些由 new (malloc)分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制。如果忘记释放,则会发生严重的内存泄漏。只有程序结束后,操作系统才会收回这些内存。

我们所使用的栈,分配方式就的就是堆的方式,一般32位系统,堆的大小为4GB。空间利用大了,但是效率缺比栈低太多了,因为栈是机器系统提供的数据结构,计算机会在底层对栈提供支持:分配专门的寄存器存放栈的地址,压栈出栈都有专门的指令执行,这就决定了栈的效率比较高。堆则是 C/C++ 函数库提供的,它的机制是很复杂的。

现在来比较一下它们的使用方式,代码如下:

#include <iostream>
#include <stack>
using namespace std;

//递归方式
void Print1(int n)
{
	if (--n != 0)
	{
		cout << n << endl;   //系统会先把Print1(4)、Print1(3)、Print1(2)、Print1(1)、Print1(0)压入栈中
		Print1(n);           
		cout << n << endl;   //当n==0时,条件不成立后,系统会把
	}                        //Print1(0)、Print1(1)、Print1(2)、Print1(3)、Print1(4)依次出栈
}

//栈的方式
void Print2(int n)
{
	stack<int> s;
	while (--n)             //先压栈
	{
		cout << n << endl;
		s.push(n);
	}
	while (!s.empty())      //出栈
	{
		cout << s.top() << endl;
		s.pop();
	}
}

//循环的方式
void Print3(int n)
{
	for (int i = n - 1;i > 0;i--) //倒着输出
		cout << i << endl;
	for (int i = 1;i < n;i++)     //正着输出
		cout << i << endl;
}

int main()
{
	Print1(5);  //递归
	cout << "---------------------------" << endl;
	Print2(5);  //栈
	cout << "---------------------------" << endl;
	Print3(5);  //循环
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

通过调试,发现递归调用堆栈的方式,如图:
依次压栈:





依次出栈:




结果如图:

三者效率相比以及使用优势:
栈:效率最低,但是空间利用率高,例如上面的Print,经过修改默认栈大小后,递归最多也只能Print(5000000),而栈则是它的好十几倍。
递归:效率排在循环后面,但是比栈的效率高很多,只是不能进行太大层级的递归,所以一般递归用在层级较为少的应用上,例如windows的磁盘遍历,相信没有人会无聊的搞一个文件夹的层级搞到几千甚至上万吧。
循环:效率最高,如果需要高效率,高的空间利用率的话,也就只能用循环代替了,虽然复杂,但却不是不能实现。

三者效率如图:
都是Print(5000000),并且把输出语句去掉.

递归的应用,如何递归遍历磁盘文件









栈应用之中缀转后缀表达式计算(C++、JAVA)
栈应用之中缀转后缀表达式(C语言版)

约瑟夫问题详解+源码

线性表之循环队列

线性表之链队列

线性表之顺序队列

线性表之链栈

线性表之顺序栈

线性表之双向链表

线性表之循环链表

线性表之单链表

线性表之顺序表

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/神奇cpp/article/detail/952447
推荐阅读
相关标签
  

闽ICP备14008679号