来Offer独家习题讲解 | Call Stack是什么?

如果你正在找工作，以下文章对你有帮助：

作者介绍

汤老师

来offer王牌讲师之一。清华大学计算机系信息学竞赛保送生，美国哥伦比亚大学计算机系软件系统实验室博士生，曾在 OSDI、CACM 等操作系统领域最顶级学术会议和期刊上发表多篇论文。曾参与 Chrome 和 Google Cloud Platform 的研发工作。

我们在上课讲到递归函数调用的空间复杂度的时候曾多次提到过call stack的概念，然而很多同学表示不太清楚。

今天我们就来讲一下call stack是什么。相信有了上一篇文章对virtual memory的介绍之后，同学们理解起Call stack来会相对容易一些。

👉点击阅读：来offer专题 | Virtual Memory究竟是什么？

Call Stack 是什么？

Call stack（通常译作“调用栈”）也是计算机系统中的一个重要概念。

在介绍 call stack 之前，我们首先来回顾一下 procedure 是什么。

在计算机程序当中，一个Procedure（通常译作“过程”）吃进来一些参数，干一些事情，再吐出去一个返回值（或者什么也不吐）。我们熟悉的Function、method、handler 等等其实都是Procedure。

当一个Procedure A 调用另一个Procedure B 的时候，计算机其实需要干好几件事。

一. 是转移控制——计算机要暂停 A 并开始执行 B，并让 B 在执行完之后还能回到 A 继续执行。

二. 是转移数据——A 要能够传递参数给 B，并且 B 也能返回值给 A。

三. 分配和释放内存——在 B 开始执行时为它的局部变量分配内存，并在 B 返回时释放这部分内存。

同学们想一下，假设 A 调用 B，B 再调用 C，C 执行完返回给 B，B 再执行完返回给 A，哪种数据结构最适合管理它们所使用的内存？

没错，是stack，因为过程调用具有 last-in first-out 的特点。当 A 调用 B 的时候，A 只要将它需要传递给 B 的参数 push 进这个 stack，再把将来 B 返回之后 A 应当继续执行的指令的地址（学名叫 return address）也 push 进这个 stack，就万事大吉了。

之后 B 可以继续在这个 stack 上面保存一些寄存器的值，分配局部变量，进而继续构造调用 C 时需要传递的参数等等。

这个 stack 其实就是我们所说的Call Stack。（这里的描述有些简化，实际当中计算机会做一些优化，如果参数和局部变量不太多的话就懒得放在 call stack 里，而是直接使用寄存器了。）

Call stack 在 virtual memory 里其实就是一段连续的地址空间，靠一个叫做 SP 的寄存器（32-bit 叫 ESP，64-bit 叫 RSP）来指向栈顶。

既然是连续的，于是它在使用上比我们理论课上讲的抽象的 stack 要更灵活一些，更接近 array 而不是 linked list，可以访问任意元素，而不仅仅是栈顶元素。（当然进栈出栈还是只能在栈顶进行。）这也就是为什么尽管它叫做 call stack，我们依然可以同时有不止一个参数和不止一个局部变量的原因。

Example

举个例子吧。假设我们有这样一段求阶乘的代码：

    00  int fact(int n) {

    01      int result;

    02      if (n <= 1)

    03          result = 1;

    04      else

    05          result = n * fact(n - 1);

    06      return result;

    07  }

当 main() 调用了 fact(n)，fact(n) 又调用了 fact(n-1)，fact(n-1) 即将调用 fact(n-2) 的时候，它的 call stack 差不多是这样：（具体情况大同小异，和编译器优化有关。）

其中每个 procedure 分配的内存区域叫做它的 stack frame（通常译作“栈帧”，吕老师译作“梦境”）。这也就解释了为什么当我们分析递归函数调用的空间复杂度时，既需要考虑 recursion tree 的深度，也需要考虑每层所分配的局部变量的大小。

对于上述 fact() 函数，它的 recursion tree 的深度是 n，这就意味着总共有 n 个 stack frame。每个 stack frame 里面除了保存 return address 和一些寄存器的值之外，还需要保存参数 n 和局部变量 result，它们都是 O(1) 的。所以 fact() 总的空间复杂度是 O(n) 的。

希望同学们能够通过了解 call stack 进一步理解空间复杂度的计算，在面试的时候一通百通。

（本文在写作过程中参考了 Randal E. Bryant 和 David R. O'Hallaron 所著的 Computer Systems: A Programmer's Perspective 第二版和第三版。）

E/N/D

求职，你只需要一门课程！

 活 动 公 告 

(以下时间均为美国西部时间)

6月23日 19:00-21:00

JingChi总部

LaiMeetup无人车高端技术讲座等你来

详情请点击阅读：

2017夏季班 火热报名中

详情请咨询来offer小助手。

报名方式

1.识别二维码，加入报名群，若群已满，请看方法2。

2.添加来offer小助手为好友，直接咨询入群。

3.如需电话咨询答疑，请发送简历到[e-mail]，我们的老师将会在24小时内联系你。

折 扣 信 息 

2个人或者2个人以上报名

团购价每个人优惠300刀

Early Bird不试听即报名

优惠500

（折扣上限为500）

 课 程 介 绍 

2017夏季班 火热报名中