数据结构系列--栈与递归 _函数

数据结构系列--栈与递归
原创慧子和她的3D慧子和她的3D今天
“栈在程序中的应用一般分两种，一：概念的递归；二：回溯算法递归。”
01
—
栈与递归
C语言中的“局部变量在栈上分配空间”‘’，与数据结构的栈，此栈是彼栈吗？
数据结构中的栈会有对应的入栈出栈操作，但C语言或者其他栈不会有。程序中的“”函数调用栈“”是栈数据结构的一种应用，在程序语言实现或者程序运行的时候，会有栈空间（这个空间用于实现程序调用中的活动记录），函数调用栈一般是从高地址向低地址增长的
栈底为内存的高地址处
栈顶为内存的低地址处
函数调用栈中存储的数据为活动记录（是函数调用过程中一系列相关信息的记录）下图为活动记录的典型：类似于结构体

文章插图
布局有：函数调用的参数，函数调用的活动地址，上一条函数调用的edp地址，函数调用时寄存器的值，函数的局部变量以及其他上下文数据，其中两个非常熟悉--参数和局部变量，这就是我们常说的“局部变量在栈上分配空间”‘’的原因，因为局部变量是存在于活动记录中的，而活动记录存在于栈空间中

文章插图
如果继续调用函数，地址指针应该请继续往下放，当指针返回时指针指向func，该行为与栈数据结构一致。在编译器工作的时候，调用一次函数就会在栈空间插入一条活动记录，每当一个函数返回的时候，就会从栈空间弹出一条活动记录。
程序中的栈空间可以看成是一个顺序栈的应用
程序中的栈空间是一定的，不会无穷大，顺序栈在创建的时候必须声明大小
栈保存了一个函数调用所需的维护信息
函数参数，函数返回地址
局部变量
函数调用上下文
什么是程序的栈溢出？
在不断压栈过程中造成栈空间耗尽而产生栈溢出
【数据结构系列--栈与递归】

文章插图
栈溢出常由于函数递归过深或者局部数组过大而造成

#include void reserve(char* s){if((s != NULL) && (*S != '\0')){severse(s+1);printf("%c",*s);}}int main(){resever("12345");printf("\n");return 0;}

该函数的作用是将输入字符串逆序打印，用递归来实现
递归调用中的栈变化

文章插图
在结束后开始退栈，弹出栈顶活动记录。先是在中，一次次恢复上次调用，不停的执行。然后弹出main的活动记录。
02
—
总结
程序栈空间在本质上是一种顺序栈。
程序栈空间的访问是通过函数调用进行的。
程序栈空间依然遵从先进后出的规则。