回复：C语言递归调用转化为栈处理的一般式, 申请精华.

2.2 运行时刻环境[Run Time Environment]
2.2.1 前言
LZ之前有两篇帖子, 一篇是《程序员的基本概念》, 一篇是《C语言函数调用的汇编级解释》,这两篇帖子都是理解C语言程序如何运行的一些基础, 都发在本贴吧之中, 找精品贴应该能找到. LZ现在简单地阐述一下.
计算机语言就是人类和计算机沟通的方式(The way to communicate with computer).
首先我们把语言分类. 目前的语言分类一般从两个角度去分, 一是该语言所遵从的范式, 二是该语言的解释/执行方式.
从语言的范式(Paradigm)上来说, 语言一般分为声明式的(Declarative Language), 函数式的(Functional Language)和命令式的(Imperative Language).
声明式的语言如Prolog(Programming in Logic). 只需要给出一个问题的"正确描述", 它就自动找到答案.
函数式的语言如erlang, haskell, clojure, 某种程度上说, 它们的主要宗派是Lisp[List Processing]. Lisp不太像是一门语言, 它没有"官方"的说法, 各种各样的实现都是Lisp.
命令式的语言. C/C++, Java, C#, Objective C等等等等. 所谓命令式, 在于"指定计算机指令执行的过程, 计算机就照此执行"的意思. C++是集多重范式于一身的语言, 命令式范式和纯函数式范式, 乱七八糟的各种范式只要程序员想要C++几乎都提供支持, 以至于LZ常常对C++的复杂性感到不可思议[换句话说C++是怪胎, 但偶尔解决某些问题时又特方便好用]. LZ最终在语言上的选择是回归简单, 由于LZ是C语言出身, 所以最终LZ手上的语言是C语言. 除C语言之外, Shell script, Makefile, Lisp scheme, sed awk LZ都略懂. C++/Java也是略懂[LZ有段时间工作时常看大段的Java(单个文件一不小心就上万行, 几十个文件的那种--当然LZ才不会傻到想去看完它们)].
语言的解释/执行方式分类某种程度上使语言有了一些"本质上的"差别.
从这个角度, 语言分为"编译, 然后执行的", 和"不需要编译, 由解释器解释执行的"语言.Java则是怪胎, 它是"编译, 然后解释执行"的混合物, 好听的说法是混血, 不好听的说法就是杂（^^)种. 另外这种差别也使得, "是否能够在运行期维护类型系统?" -- 这种差别导致了静态类型和动态类型的区分.
============> 分割线 <============
LZ现在废话好多... 难道是因为LZ退出开发生涯并从事了讲师这个职业的原因吗...
============> 分割线 <============
OK... 正题开始...
C语言是静态弱类型的编译型语言.
静态类型是说它的类型系统只在编译期存在. 弱类型是说它允许不一定(运行期)安全的隐式类型转换. 编译型语言是说它必须要先编译然后执行.
静态类型限制程序员太随意自由; 弱类型给予程序员自由; 编译型就是说它写出来的程序运行时非常快, 非常非常快, 目前没有比它更快的高级语言, C语言就是高级一点的汇编而已.而且, 如果汇编代码写得挫, 未必就比C语言快, 因为编译器的优化偶尔是很恐怖的. 汇编码的优势在于有时有C语言有无法操作到的东西, 比如CPU内部寄存器, 这一点一般通过C语言内嵌汇编码来解决.
============> 分割线 <============
既然是编译型语言, 那么自然需要编译了.
目前来说, 大多C语言实现, 都将编译C语言分为4步.
第一步是预处理. 就是处理掉宏, 还有包含头文件之类的事情.
第二步是编译, 这是真正的编译, 这一步把C语言代码转化为对应平台的汇编码. 这一步是由C语言编译器(也就是通常说的C语言实现)来做的.
第三步是汇编, 这一步将汇编代码转换为目标文件. 目标文件已经不是纯文本文件了; 目标文件是二进制文件. 在目标文件中, 所有的代码段以地址0开始, 所有的数据段以地址0开始.
第四步是链接, 这一步将各个目标文件中的代码段汇总, 将各个目标文件中的数据段汇总, 然后给予汇总的代码段和数据段以运行时起始地址, 并解决和动态库的符号链接问题, 如果是静态库则当作一般目标文件一样处理.
以上这四步通常统称编译期(Compiler Time). 因为这是一个C语言程序从源代码构建出来开始出生的过程, 因此通常就称之为编译或者构建了, 因为其中最主要的步骤是第二步也即编译[实际上每步都很重要].
============> 分割线 <============
在上面的4步需要用到的工具, 即, 预处理器, 编译器, 汇编器, 链接器, 统称为编译工具链[Compile Chain]. Linux系统上的GCC, 即GNU Compiler Collection, 亦可称之为GNU Compile Chain. 不过, 链接器因为目标文件/二进制文件处理的原因, 在其代码维护中被放到binutil[ Binary Utilities , 二进制工具]一类了.
其实...要说吧, 是否理解这四步中的工具到底做了什么, 还有一些二进制工具该怎么用, 其细节如何, 通常已经是区分一个C程序员是否经验老到的标志了. 一个经验老到的C程序员, 清楚他所写下每一个字节. 话题太长, 不便展开. 这些东西虽然基础, 但对C程序员来说实际上极为重要(通常它们也是C程序员理解计算机系统的极其重要的途径). 不过毕竟只是程序员的基本功底, 东西要称得上"计算机科学", 怎么都得和可计算理论和各种算法沾边, LZ本文描述的只是基础, 而不是"计算机科学".

2.2.2 运行时刻环境
当C语言程序被构建为一个可执行程序之后, 它还是一个文件 -- 虽然它是一个二进制的可执行文件. 它静静地躺在硬盘中, 等待程序员, 或者别的什么人去执行它.
假设这个程序叫做app. 当程序员在shell命令行上敲下:
./app
或者, 当某人在windows系统中, 用鼠标双击了某个文件...
于是, 此时程序开始运行.
程序开始运行, 此时, 就是程序运行期[Run Time]的开始.

============> 分割线 <============
程序在开始运行之前, 其实还有事情要做的.
这个要做的事情叫做加载(Load).
简单地说, 就是把文件从硬盘上挪到内存中.
现代操作系统一般借助于现代CPU的异常处理来完成加载步骤. 这个异常一般称之为缺页异常. 在Linux Kernel中, 做异常处理的函数名字大约是叫do_page_fault.
细节不用关注太多. 总之一句话, 程序需要加载才能运行. 如果此时有操作系统，那么完成加载的就是操作系统，通常操作系统就是加载器. 如果此时连操作系统都没有，那么程序员需要把这段二进制文件先做成一个磁盘镜像，或者做成一段放到FLASH中的东西，或者...不同的CPU有不同的指定。一般来说，任意CPU都会在起电后跳到某个指定物理地址去执行。把这段二进制代码放到那个指定地址去它就会运行。这些代码一般都被早前的程序员们写得很成熟了，它们一般被叫做BootLoader或者BIOS.
程序在加载之前, 该程序文件中已经有了分段/节(Section). 也即是说, 在二进制文件中, 所有的程序指令被分到一个Section, 所有的程序数据存储空间被分到一个Section, 文件中存储二进制程序指令的Section被称之为.text Section也即代码段, 文件中存储所有全局初始化数据/静态初始化数据的Section被称之为.data Section也即数据段.
当看C语言的基础书籍时, 里面提到的“静态存储区”，就是指二进制文件中的数据段。
很显然，静态存储区在加载后在内存中它也被称之为静态存储区。代码段被加载到内存中之后它仍然被称作代码段。
============> 分割线 <============
问题出现了。
文件中的静态存储区大小是有限的[意味著，被加载到内存中之后，它的大小也是固定不变的]。就是说，静态存储区在编译期已经规划好。
可是现在来到了运行期。C语言中有局部变量。函数中的局部变量在函数被调用时开始生存，在函数返回后，它被销毁。
还有。C语言中有指针，指针的基本用处表现在它能动态地获取内存区域，能malloc, 能free.
在程序加载开始运行时，这些问题必须要解决。
============> 分割线 <============
没错。前面提到了栈。栈即为C语言的运行时环境，用来完成存储函数中局部变量的事情。
堆则用来在运行时刻给C语言中的指针分配内存。

2.2.3 进程栈/线程栈
figure 2.2
===============================================================
@@ main <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< stack base
@@@@ --> func1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< stack frame 1
@@@@@@ --> func2 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< stack frame 2
@@@@@@@@ --> ...
@@@@@@@@@@ --> func_i <<<<<<<<<<<<<<<<<<<<<<<<<< stack frame i
@@@@@@@@@@@@ --> func_return <<<<<<<<<<<<<<<<<<< stack top
===============================================================
见figure 2.2. 注意到这个图和figure2.1并没有本质的区别. LZ通过这个图来解释进程栈和函数调用链.
main, func1, func2...都是函数. 这些函数都有自己的局部变量. stack base, stack frame 1, stack frame 2...都是栈帧. 把函数中的局部变量理解成盒子. 把局部变量中的值/状态理解为盒子中装的东西. 把stack frame[栈帧]理解为箱子, 箱子用来装盒子.
我们假设，程序开始执行时从main函数开始[毫无疑问，这只是个假设]。
于是figure 2.2描述了一个函数调用链，这个函数调用链的执行路径是这样的：
1. 调用
main ==> func1 ==> func2 ==> ... ==> func_i ==> func_return
2. 返回
main <== func1 <== func2 <== ... <== func_i <== func_return
于是，这个路径和 LIFO 又是完全契合的。
如果每个函数都把它自己的所有局部变量(盒子)放到栈帧(箱子)中，
比如, main函数在调用func1之前，把自己所有的盒子先放到叫做stack_base的箱子中, 然后跳转到func1那去执行. func1在调用func2之前, 把自己的盒子先放到叫做stack_frame1的箱子中, 然后跳转到func2那去执行. 如是, 直到函数func_return被函数funci调用并开始执行. func_return也一样把自己的盒子放到叫做stack_top的箱子中.
func_return执行, 并可能改变stack_top箱子中的盒子中的内容. 然后它发现自己没事可干了, 因为它的代码执行完了，它该返回了. 它返回的意思就是说stack_top箱子中的内容没有用了 -- C语言函数不正是这样的吗[先用stack_top箱子, 装传入的参数/变量/盒子, 然后它可能改变传入的参数, 然后它执行完了, 该返回了, 于是它的箱子和盒子都没用了]. 既然箱子没有用了, 那么就可以把它销毁[至于返回值 -- 返回值是属于调用方的盒子, func_return只是负责把返回值计算出来, 至于调用方要不要, 或者拿去干什么, 它是不管的].
同理. func_i等到func_return执行完, func_i接下来执行调用func_return之后的代码. 然后func_i也执行完了. 于是func_i的箱子也没用了, 于是销毁掉.
于是:
1) 建立栈帧并调用
main ==> func1 ==> ...... ==> func_return
stack base ==> stack frame1 ==> ...... ==> stack_top
2) 销毁栈帧并返回
main <== func1 <== ...... <== func_return
stack base <== stack frame1 <== ...... <== stack_top
没错, 这就是函数调用链和栈的关系和总结. 它们的路径都是 LIFO 的.
箱子总要有个地方放对吧。没错。于是在程序开始运行前，操作系统给程序指定一个放箱子的起始地址，诺，你把箱子从那个地方开始叠。这个指定的地址就是栈底。然后函数开始执行，开始调用，开始叠箱子。每次正在执行的函数都只能访问自己的箱子，也就是栈顶的那个箱子。
如果没有操作系统给指定起始地址怎么办？这时候既然操作系统都没有，那就程序自己干。方法是嵌入一段汇编码。
进程栈/线程栈阐述得差不多了。之所以叫进程栈，是因为运行起来的程序一般不再称之为程序，而称之为进程。进程的栈自然就是进程栈了。
线程栈呢？ -- 一个进程里面有多个线程怎么办呢？简单，一个函数调用链对应一个栈呗。既然这个函数调用链被称之为线程，那么这个函数调用链所对应的栈就叫线程栈。

擦...
终于...终于要开始讲递归了.
其实关于进程栈/线程栈中还有一些细节，... 嗯, 讲化解的时候会提，不码了。
累, @ 御坂美琴みさか
炮姐, 就叔叔前面码的这些字，也能给精华了吧...

终于要开始讲递归了...
关于栈还有一些实现细节... 算了，以后再说吧。码字好累。
......

话说c是规定一定要编译的吗？
我记得好像有个什么c解释器的..

算了。加码一节，免得后来解释麻烦。
2.3 关于进程栈的一些实现细节
在2.2.3 figure 2.2中，LZ给出了:
1) 建立栈帧并调用
main ========> func1 =========> ...... ==> func_return
stack base ==> stack frame1 ==> ...... ==> stack_top
2) 销毁栈帧并返回
main <======== func1 <========= ...... <== func_return
stack base <== stack frame1 <== ...... <== stack_top
这里有个实现细节要考虑。
童鞋们肯定会说：我确实写了一个C语言函数(func1)并让它调用另外一个C语言函数(func2)。可是我没有建立栈帧呀？我也没有销毁栈帧呀？那栈帧是怎么建立的，怎么销毁的？
C语言函数是不是要被编译器编译成汇编码啊？是的。
那编译器能不能在编译C语言函数的时候在函数开头部分和函数结束部分插上汇编代码啊？可以。
所以编译器会在函数开头插入建立栈帧的汇编代码；在函数返回前插入销毁栈帧的汇编代码。请参见LZ的《C语言函数调用的汇编级解释》。这里略提。
栈帧，也即箱子，直观地画就像下面这样子：
figure 2.3
|------------------|
|main 函数栈帧,====|
|即, main函数的箱子|
|------------------|
|------------------|
|func1函数栈帧=====|
|------------------|
|------------------|
|======*****=======|
|------------------|
|------------------|
|func_return函数===|
|栈帧==============|
|------------------|
这些箱子其实是连在一起的。下面画出最顶层的箱子。栈顶指针一直指向最顶层的箱子。每个箱子都大同小异，每个箱子中的细节是：
figure 2.4
|-----------------------|
|参数i==================|
|参数i - 1==============|
|参数...================|
|参数0==================|
|-----------------------|
|Program Counter[eip/rip on x86/x86_64]
|-----------------------|
|Stack Base Pointer[ebp/rbp on x86/x86_64]
|-----------------------| <====== Current Stack Base Pointer
|now, contianer,========|
|to save those auto var=|
|or status here=========|
|-----------------------| <====== Stack Top Pointer一直指向这里,
================================== esp/rsp on x86/x86_64
其中, Program Counter即程序计数器，是放的返回到调用方时要用的返回地址。参数和PC都是调用方放进来的，因为调用方才知道该传什么参数给被调用函数，调用方才知道调用完函数后该返回到哪里。Stack Base Pointer放的是调用方的栈基地址，Current Stack Base Pointer即当前栈帧的栈基指针，Stack Top Pointer一直是当前正在执行的函数的栈顶指针。
基本上，
[下面代码中,]
[rbp代表ebp/rbp on x86/x86_64] 栈基指针
[rsp代表esp/rsp on x86/x86_64] 栈顶指针
[pc代表eip/rip on x86/x86_64] 程序计数器，或者正在执行指令的下一条指令的地址
1. 调用方Caller调用函数的汇编代码是：
push 参数i
push 参数i - 1
push 参数...
push 参数0<========>此处设i个参数总共占用4i/8i个字节
call callee_addr [== push pc, jmp callee_addr]
add $4i/8i, %rsp
2. 被调用方Callee被调用函数的汇编代码是:
// 入口代码，entry code:
push %rbp
mov %rsp, %rbp
push %可能破坏的寄存器
sub $num, %rsp [num代表局部变量/盒子至少需要的空间, 或者更多]
===============[sub这一步就是为局部变量分配空间]
// 出口代码, exit/return/out code:
leave [== pop %可能破坏的寄存器, mov %rbp, %rsp, pop %rbp]
ret [== pop pc, jmp caller_addr]
========================================================
码完. 睡了...
========================================================

=========================> Chapter 3 <=========================
递归的形式
===============================================================

马克

深坑什么的，先马克一下好了

@ 良化纲领_
对LZ的文章提出了一些问题。
1. 确实，LZ的文章中关于进程栈的阐述隐含了一些前提：就是LZ阐述的是用户栈，当用户线程/进程陷入内核时，内核栈中必须有关于用户栈的处理。
但是LZ毕竟不是阐述内核的，若然对内核已经有较深的认识，很显然LZ的这部分阐述可以略过；若然对系统用户栈还没有认识，那么LZ的阐述实际上在用户程序方面上的考虑已经足够。
因此，在此提醒一下：LZ阐述的是用户栈，而且，通常都隐含了目前具有操作系统环境这一前提条件。
2. LZ说加载是依赖于PF的，这个确实不尽然。但是加载这一步骤是必须的；而且目前的主流CPU和实现，加载都是依赖于PF的。
3. 关于malloc/free, 确实C语言中的指针并不要求一定要能够动态获取内存，或者说，动态获取内存是实现相关的。不过实际上如果不能动态获取内存，指针的用处立刻显得很苍白。所以在隐含有操作系统环境的前提下，LZ的阐述仍然没有问题。
===============================================

@Hope_20121221_
指出了，C语言实现未必就是编译型的。
嗯，C语言标准绝对没有指定说C语言一定要是编译型实现。不过考虑到“真正有用的C语言实现”和目前的主流实现，LZ仍然将其看作为编译型实现的语言。

===============================================
感谢以上两位对LZ文章的说法提出质疑。LZ表示欢迎~
另外，大多数童鞋不必太担心LZ此文是否具有误导之嫌。LZ尽量不要误导大家。当童鞋们达到如上两位一样能够对LZ文章提出质疑的程度时，LZ的文章也自然已是过去式；倘若LZ此文确实对童鞋们有帮助，则甚好。
######################

另外，关于2.3节，进程栈的实现细节中，
实际上，rbp [register base pointer]并不是必须的。
唯一必须的是，pc 和 rsp [register stack pointer]. pc用来指出，函数执行完毕后应该返回到哪里；rsp用来指出，当前栈顶在什么地方。
现在的大多数编译器，比如GCC，可以直接根据rsp，偏移一段来取得局部变量和参数。这个是在编译期可计算的。实际上，大多数发布版本的软件，都通过一个编译器选项去掉了栈帧中的rbp.
以上。下面开始本文中真正重要的内容。

##############################################
第三节的内容可能才是本文中最重要的东西。
##############################################