当前课程知识点：数据结构 > 第3章 栈和队列 > 3.4 栈与递归 > 讲解（下）
刚才，我们看了几种类型的递归问题
那栈与递归又有什么关系呢
递归算法通常看起来步骤比较简单
代码很简洁
但是它们的执行过程却比较复杂
每次递归的时候
需要暂存当前的参数、语句地址
这是因为，我们写一个程序
如果去调用其他函数
将来被调函数执行完之后，我们要返回到调用处
那么，CPU怎么知道返回到哪个位置呢
那只有在跳到被调函数之前
我们将调用处的这行语句的地址
包括相关的一些参数
把它们存到某一个位置
将来，被调函数结束之后
我们再从这个位置，取得之前保存的那些地址
从而才能跳回到调用处
我们现在以函数调用为例
假设，在main函数当中，调用了f
那么，程序流程会从f调用处，转到f的定义处
假设，在f当中又调用了g函数
那么，又会从g
这一行函数调用，转到g的定义处；g当中又调用了h
那么，又会转到h的定义处
当h函数执行完了之后
应该返回到哪里，继续执行呢？很明显，应该返回到g当中
调用h的这行语句，继续往下执行
g执行完了，又要返回到f当中
调用g的这行语句，继续往下执行
然后，又要回到main当中
调用f的这行语句，继续往下执行
如果main函数执行完了，整个程序就执行完了
这里，红色的箭头就代表着返回
我们会发现，那些后被调用的函数，总是先返回。你看
f、g、h调用的时候，是先调用f
再调用g，再调用h
但是，返回的时候
先返回到h的调用处
h调用结束之后，再返回到g的调用处，再返回到f的调用处，又出现了先什么后什么这样的描述
那么，看到这样的描述
马上联想到栈
对于计算机来说
递归调用，也就是函数自己调用自己，和函数
调用普通的函数，是没有区别的
因为，无论是调用其他的函数
还是调用自己
CPU都要将相关的地址和参数入栈
所以，从这点上来说
递归和普通的函数调用没有什么差别
而且，将返回地址入栈
这样一个操作
对于编程者来说是透明的
它由系统自动地维护
压栈和出栈的操作
在函数调用的时候，编译出来的机器码会自动产生PUSH指令
当被调函数返回的时候
编译出来的机器码会自动产生POP指令
下面，我们以刚才介绍的求阶乘为例
看看一个递归程序
在执行过程当中，递归工作栈的状态是如何变化的
这个函数，是我们刚才写的递归形式的求阶乘
为了方便描述
我用的是if-else语句
没有用最简化的、带条件运算符的唯一一行语句
我们在main函数当中第11行调用了f，传入的参数
是3
程序从main开始执行
执行到第11行的时候
由于调用了f，那么，程序的执行流程会跑到f的定义处
也就是第1行
在转到第1行之前
因为，将来f结束之后
要回到第11行继续执行
也就是把f(n)的结果赋值给v
因为第11行还没执行完
所以，为了能够让它回到11行
我们在转到f之前
先要将第11行的地址，也就是这个灰色的(表示地址)
还有当时的一些参数
我们这里只管这个n
转到被调函数之前
调用处的这行语句地址和当前的一些参数
把它们放到栈里面
这时候，n的值是3
我们转到第1行去执行，第1行，由于n等于3
那么，要执行第5行
注意，它返回的是3*f(2)
f(2)的结果还不知道
因为要继续递归
准备又回到第1行
为了方便大家去分析
我并没有用这一份代码，反复地去递归；我把代码复制到右边
以方便大家分析，这两份代码是一模一样的
现在，程序执行第5行，准备跳到第1行，准备跳到这一行
为了将来能够回来，计算
3*f(2)
那么
我们必须将第5行的地址，将它保存起来
同时，将当前的参数n也保存起来
那是5和3，被放到了栈里；现在，程序又跳回到第1行
这时候，参数的值是2
由于2不等于0
又要执行第5行
那么，返回2*f(1)
程序又要准备跳回到第1行
在跳之前
我们又要将这一行的地址保存起来
就是5和2，这时候n的值
实际上是2
我们又复制了一份代码
跟原来是一样的
这时候
由于参数的值是1
依然不满足这个if条件
又要执行第5行
这时候，返回1*f(0)
准备又要跳到f的第1行了
那在跳之前
我们又要将这一行的地址，保存到栈里面
同时，保存当前的
n的值
它是1；跳到第1行
这时候，n的值是0，满足了if条件
这时候，直接return
我们说过，return是结束函数的运行
它编译成机器码的时候
实际上，会产生POP指令
POP指令就是将栈顶里面保存的地址和参数
将它们弹出到相应的位置
我们从第3行返回，返回到哪儿呢
CPU怎么知道返回到哪呢
实际上，要返回的地址已经在栈顶保存起来了
我们就返回到第5行
而且，返回到第5行的时候
n的值是1
1*f(0)，因为f(0)在刚才执行第3行的时候，返回的是这个1
所以1*1
它是等于1的；第5行
作为这次调用的最后一行语句
它也要返回，返回的时候，又要从栈顶当中取出地址和当时的参数2，那么返回到这里，计算2*1
它也是返回语句
那么，再从栈顶当中，弹出5和3这样的地址和参数
返回到这里
计算3*2
f函数调用结束了
下面要回到主函数
它怎么知道回到主函数中哪一行呢？一样的，从栈当中取出11这个地址和3这个参数，回到这里
因为，f(3)
我们刚才计算出来了，是6
所以，这时候f(n)的结果就是6
然后继续执行
第11行，将6赋值给v，继续往下执行
从这个例子
我们发现
对于计算机来说
函数无论是调用自己，还是调用其他的函数，都是一样的
都要将调用处的地址和当时的一些参数，把它们入到栈里面去
被调函数执行完之后
再从栈顶当中，弹出之前保存的地址和参数
以便CPU知道，从哪个位置开始，继续往下执行
我们将转到被调函数前入栈的这些操作
称为保护现场
这实际上是汇编语言里面的称法
同样的，被调函数结束的时候
返回的时候，我们要从栈顶当中弹出相应的地址
这时候的出栈操作
有时候也称为恢复现场
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
