3.3 栈与递归的实现

01

栈与递归

1、栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接调用自己的函数，称做递归函数。

2、在高级语言编制的程序中，调用函数和调用函数之间的链接及信息交换需要通过栈来进行。

02

实现

1、当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成3件事：

（1）将所有的实在参数、返回地址等信息传递给被调用函数保存。

（2）为被调用函数的局部变量分配存储区。

（3）将控制转移到被调函数的入口。

2、从被调函数返回调用函数之前，系统也应该完成3件工作：

（1）保存被调函数的计算结果。

（2）释放被调函数的数据区。

（3）依照被调函数保存的返回地址将控制转移到调用函数。

3、一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调函数是同一个函数，因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！