当函数执行完毕后，如何返回调用处？

周立功教授数年之心血之作《程序设计与数据结构》以及《面向AMetal框架与接口的编程（上）》，书本内容公开后，在电子行业掀起一片学习热潮。经周立功教授授权，本公众号特对《程序设计与数据结构》一书内容进行连载，愿共勉之。

第二章为程序威廉希尔官方网站 ，本文为2.3 栈与函数返回。

当函数执行完毕后，如何返回调用处呢？由于该函数可能会被多次调用，且每次调用的地方很可能不一样，这样被调用函数也就不可能知道自己该返回到哪里，因此在调用函数时必须告诉被调用函数应返回到哪里？

>>> 2.3.1 堆栈

为了保存变量（数据），通常计算机会提供非常多的内存。为了便于管理内存，将所有变量使用的内存称为栈，而将未分配的内存区域称为堆。这些未分配的内存区域，程序员可以块为单位请求它。这部分内存是由操作系统管理的，一旦一块内存被分配出去，它只能由分配了这块内存的原始代码使用，并使用指针访问这块内存。由于内存是稀缺资源，当程序不再需要该内存时，都应该释放回去。如果不这样做，程序将会耗光内存，导致运行速度下降甚至崩溃。这就是因为程序员没有释放本应释放的内存，造成了所谓的内存泄漏。

堆和栈是两种常用的数据结构，主要用于数据的动态存储。当程序执行时，栈中存储的是程序的执行过程，比如，main()函数的局部变量argc和argv都在栈中，而使用malloc()函数动态分配的内存是存储在堆中的，堆栈共享同一块内存区域。通常程序栈占据这块区域的下部，而堆用的是上部。当调用函数时，函数的栈帧被推到栈上，栈向上“长出”一个栈帧。当函数终止时，其栈帧从程序栈弹出。虽然栈所使用的内存不会被清理，但最终可能会被推到程序栈上的另一个栈帧覆盖。动态分配的内存来自堆，堆向下生长。随着内存的分配和释放，堆中会布满碎片。尽管堆是向下生长的，但这只是大体方向，实际上内存可能在堆上的任意位置分配。

平常大家所说的“堆栈”主要是指栈，计算机在硬件上直接支持栈。在计算机科学中，栈是一个抽象的概念。它的抽象行为特征是栈可以存储相同类型的数据，通常又将栈中的数据称为元素。只允许向栈中压入一个元素（即入栈push），或从栈中删除一个元素（即出栈pop），且元素按照“后进先出”原则处理（last in，first out，LIFO），禁止测试或修改不在栈顶的元素。

图2.7 四种栈示意图

如图2.7所示为通用计算机4种形式的栈，分别称之为满递减堆栈、空递减堆栈、满递增堆栈和空递增堆栈，这些都是栈的物理结构。其中的“递减”是指数据入栈时堆栈指针的值减少，即堆栈从高地址向下增长，就像钟乳石一样。“递增”是指数据入栈时堆栈指针的值增加，即堆栈从低地址向上增长，就像石笋一样。而“满”是指SP指向的存储单元保存最后入栈的数据；“空”是指SP指向的存储单元将保存下一个入栈的数据。4种形式的栈都对应相同的逻辑数据结构，本书后续章节除非特殊说明，否则均以“满递增堆栈”为例。

>>> 2.3.2 入栈与出栈

假设允许入栈和出栈数据为int，即sp为(int *)类型变量。如果入栈的数据小于sizeof(int)个字节，则需要将其转换成int类型数据才能入栈，且出栈后也要进行相应的类型转换。对于入栈的数据大于sizeof(int)个字节，则只能拆分数据，一次入栈数据的一部分，通过多次入栈完成整个数据的入栈；而出栈这个数据也要多次，全部出栈后再组合成原始数据。

1. 入栈（push）操作

如果将sp当作(int *)类型的变量，则对于满递增堆栈来说，将数据data入栈用C语言描述如下（详见图2.8）：

图2.8 入栈操作示意图

如果data的长度大于sizeof(int)，则需要将数据拆分后多次入栈，入栈的顺序可以先低位后高位，也可以反过来。如果入栈的顺序为先低位后高位，其示例详见程序清单 2.27。

程序清单 2.27 先低位后高位顺序入栈示例

这里假设data可以象整数一样移位，且sizeof(data)是sizeof(int)的4倍。

2. 出栈（pop）操作

如果将sp当作(int *)类型的变量，则对于满递增堆栈来说，将数据出栈用C语言描述如下（假设出栈的数据保存到变量data中，详见图2.9）：

图2.9 出栈操作示意图

如果出栈数据data的长度大于sizeof(int)，则需要多次出栈后拼接数据，其拼接的顺序为入栈的反序。如果入栈的顺序为先低位后高位，详见程序清单 2.28。

程序清单 2.28 先高位后低位顺序出栈示例

这里假设data可以象整数一样进行位操作，且sizeof(data)是sizeof(int)的4倍。

>>> 2.3.3 函数的调用与返回

在讨论ADT栈之前，首先看一种用于处理程序运行时的函数调用的系统栈。每当函数被调用时，系统首先创建一个称作活动记录或栈帧的结构，将其放在系统栈的栈顶。初始时，被调函数的活动记录只包含一个指向前一个活动记录的指针和一个返回地址。前一个活动记录的指针指向调用函数的活动记录，而返回地址包含的是函数调用结束后下一条执行语句的地址。因为在任何时刻只有一个函数被执行，所以被执行的函数就是活动记录位于系统栈栈顶的函数。

如果该函数又调用其它函数，那么函数中的局部变量（静态局部变量除外）及其参数也将加到其活动记录中，然后为被调函数创建一个新的活动记录并存放在系统栈栈顶的函数。当被调函数结束时，删除该活动记录。此时调用函数的活动记录又位于系统栈的栈顶，继续运行该函数。

C语言通过硬件栈保存函数的返回地址，被调用函数将返回地址出栈到程序计数器PC中，以返回到调用点，其示例代码详见程序清单2.29。

程序清单2.29 函数的调用与返回示例

对于程序清单2.29（10）来说，用C语言描述如下：

对于程序清单2.29（5）来说，用C语言描述如下：

由此可见，当调用函数时，将主程序代码行的下一条指令的地址保存到栈中；当函数返回时，程序就会从栈中获取该地址，并从那一点继续向下执行。在函数调用了其它函数的情况下，将每一个返回地址都放到栈中；当函数结束时，就可以找到它们在栈中的地址。