没有更多推荐了，
不良信息举报
举报内容：
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！「C语言书籍」《495个C语言问题》「C语言书籍」《495个C语言问题》边澄澄百家号《你必须知道的495个C语言问题》作者: Steve Summit出版社: 人民邮电出版社译者: 孙云 / 朱群英出版年: 2009-2页数: 262定价: 45.00元装帧: 平装丛书:图灵程序设计丛书ISBN: 9内容简介“本书是Summit以及C FAQ在线列表的许多参与者多年心血的结晶，是C语言界最为珍贵的财富之一。我向所有C语言程序员推荐本书。”——Francis Glassborow，著名C/C++专家，ACCU（C/C++用户协会）前主席“本书清晰阐明了Kernighan与Ritchie《The C programming Language》一书中许多简略的地方，而且精彩地总结了C语言编程实践，强烈推荐！”——Yechiel M. Kimchi，以色列理工学院C是一门简洁精妙的语言，掌握基本语法容易，真正能够自如运用，就不那么简单了。你难免会遇到各种各样的问题，有些可能让你百思不得其解，甚至翻遍图书馆，也找不到问题的答案。本书的出版，填补了这一空白。书中内容是世界各地的C语言用户多年来在新闻组comp.lang.c中讨论的结晶。作者在网络版C FAQ列表的基础上进行了大幅度的扩充和丰富，结合代码示例，权威而且详细深入地解答了实际学习和工作中最常遇到的495个C语言问题，涵盖了初始化、数组、指针、字符串、内存分配、库函数、C预处理器等各个方面的主题。许多知识点的阐述，都是其他资料中所没有的，弥足珍贵。作者简介Steve Summit 著名的C语言专家。Usenet C FAQ的创始人和维护者，有近30年的C编程经验。毕业于麻省理工学院。他曾在华盛顿大学教授C语言课程多年。除本书外，他还与人合著了C Unleashed一书。如果对这本书感兴趣，可以私信回复“C语言”领取。本文仅代表作者观点，不代表百度立场。系作者授权百家号发表，未经许可不得转载。边澄澄百家号最近更新：简介:说给岁月的情话，其实都无关风月。作者最新文章相关文章C语言中递归问题？ - 知乎125被浏览<strong class="NumberBoard-itemValue" title="1分享邀请回答void PrintN(int N) {
if(N == 0) return;
//[1]回归条件;
PrintN(N - 1);
//[2]递推;
printf("%d, ", N);
//[3]当前 case 的工作;
（ps：评论里有网友指出，上面代码中第一句原来写错了，让我纠正过来。）这个函数里，很清晰的展现了递归函数的组成部分：其中：[2] 和 [3] 组成基本逻辑。递归的 idea 和数学归纳法是同一个思路。数学归纳法是：（1）证明 case 0 成立；（2）如果 case i 成立 =& 则 case ( i + 1 ) 成立。在这个问题里，定义函数 PrintN ( by argument N )
means: 打印从 1 到 N 的一系列数字。因此，该函数的实现逻辑是：（1）打印出从 1 到 N-1 的一系列数字。即调用 PrintN ( N - 1) ；这是 PrintN 的定义；（2）然后打印出 N；分别对应了代码中的 [2], [3] 。然后找出回归条件，本例子中，就是 PrintN 打印的一系列数字是从 ？ 开始的，假设从 N1 开始，则应该在 case N & N1 时回归。也就是说回归条件是：（3）if ( N & N1 ) 本题目中，N1 = 1；对应于代码中的 [1];因此上面的函数也等价于：void PrintN(int N) {
if(N & 0) {
PrintN(N - 1);
printf("%d, ", N);
现在来思考下，调用 PrintN ( 4 ) 时，用缩进来表示就很好理解了（请在 PC 上查看）：call PrintN(4)
|-- call PrintN(3)
|--call PrintN(2)
|--call PrintN(1)
|--call PrintN(0); //
|--printf 1; // output 1, return from PrintN(1);
|--printf 2; //output 2, return from PrintN(2);
|--printf 3; //output 3, return from PrintN(3);
|--printf 4; //output 4, return from PrintN(4);
当然，你还可以在草稿纸上，绘制出在调用过程中， stack 上的函数的 stack frame 堆叠时的即时状态的变化过程。需要你对汇编层面有一定了解。上面的图，从上向下看的方向，是时间 “t” 坐标轴，从左向右看，是 stack （或者说是 SP ）坐标轴。两者结合在一起，你会看到栈的动态变化过程，相当于：在栈“上方”（开口方向），放一个“盒子”里面装着4 （除此外，盒子里还有一个地址，那就是 [3] 所在的指令地址），然后在上面再堆个“盒子”，里面装着3，... 一直到 0 ，然后再从最上面的盒子开始，逐个去掉。stack:
---------------------
| 4 | 3 | 2 | 1 | 0 | --& 栈增长方向
---------------------
call PrintN(4) //push 4
call PrintN(3) //push 3
call PrintN(2) //push 2
call PrintN(1) //push 1
call PrintN(0) //push 0
PrintN(0) ret
//add esp, 4
PrintN(1) ret
//add esp, 4
PrintN(2) ret
//add esp, 4
PrintN(3) ret
//add esp, 4
PrintN(4) ret
//add esp, 4
当前的 case （调用所在深度/层次），由 栈 （ESP）追踪，也就是说，例如：调用 printf 时，打印的数字是 [ ESP + 4 ] 。也就是说，栈使得计算机”记得“在每个 case 中应该打印的数字是几，同时”记得“函数调用后从什么位置继续取指。运行时，由 IP （上层叫 PC，底层叫 IP）追踪”指令流“。递归的执行过程，是以上两者的协作。当然，从底层看，递归和普通的函数调用的唯一区别就是该函数调用的其他函数中，是否包括自身，从 CPU 执行指令的视角来看两者没什么区别和不同。--最后补充下，对此函数， VC2005 的 release 的编译结果：sub_401000 void PrintN (int N)
arg_0 = dword ptr 8 {
mov esi, [esp+arg_0]
/* int esi = N; */
lea eax, [esi-1]
/* int eax = N - 1; */
jz short loc_401015
if(N-1 == 0) ---------|
call sub_401000
PrintN (N-1); ----+---|
add esp, 4
loc_401015:
printf("%d, ", N); &--|
push offset aD
/* string("%d, ")'s address */
add esp, 8
--日 补充：前些天有知乎网友看了我的答案后，给我发信，问我一个递归函数相关问题。它问的问题大概相当于，fact 函数返回值保存在了哪里？所以就他提出的问题，我在周末写了一个演示 DEMO （事后发现该 DEMO 大约正好接近 2000 行代码的规模，不自觉间，才发现我居然写出了几乎 1000 行代码 / 天的巅峰速度，而且可维护性始终在我控制之中没有降低，已超越了我自己早年创造的 800 行 / 天的速度记录，那时候虽然快但是代码的可维护性因为写的太快而有一点失控有所降低。而且之前不太涉及美工的东西，本次还包括了美工，美工非常耗时，我花在美工方面的时间有时会和编码时间相当。），来演示递归函数，调用执行的过程。通过观察演示程序，你可以看到，调用方（也包括 fact ）如何处理 fact 的返回值，并最终计算出 fact(4) 的结果。也可以看到，在寄存器和 stack / “主存” 的配合下，CPU 是如何严谨的根据指令 / 代码段的指示完成运算的，包括此过程中，stack 的动态变化。我模拟了在汇编语言层面的执行过程。同时，我用 DEBUG 版本中采用的用 EBP 作为 stack frame 寻址基础的方法，因为这样的汇编代码，看起来更易读一些。演示程序截图如下（下图显示了调用深度最深时的状态）：截图经过我的编辑，画出了每个调用深度上的 stack frame 。那些大括号等在 DEMO 中是没有的（只有右侧绿色的备注）。ESP 相当于指向右侧 stack cells 的“最下端”。右侧的 stack 分配和释放，体现在右侧的 stack 向下增长和缩回，释放空间时，将会擦除相应的 stack cells。通过设计和建立模型，模拟了 fact 函数需要用到的 CPU 指令。包括取指，（译码）执行，以及操作数的三种寻址方式（立即数，寄存器名，寄存器间接）。演示过程，和使用 IDA 反汇编时的体验非常接近。stack 承载了“记忆”函数内临时变量，参数，返回地址，保护寄存器等作用。该 DEMO 的可执行文件（EXE）的下载链接：该 DEMO 源代码（CPP） 和 可执行文件 （EXE）的下载链接：（VC 2005）----stack frame （栈帧）：函数的 stack frame 是栈上的一段空间，由：stack bottom direction (高地址方向）（1）protected EBP（也可能没有）；&----EBP（2）被保护的寄存器。（3）函数内临时变量。（4）调用其他函数时的被 push 的参数。&--ESPstack top direction (低地址方向）组成。其中 （1）EBP 也属于（2）（被保护的寄存器），因为 EBP 在函数中的功能很特别，所以把它单独列出。本例中的函数，采用的是默认的 C 调用约定，所以由调用方负责清理（4）。调用方释放调用其他函数的参数的栈上空间，这个步骤也被称为栈指针平衡。其形式如下：例如对于这样的一个函数： void foo(int arg1, int arg2, int arg3);push arg3 调用方把参数 push 到栈上；push arg2push arg1 跳转到被调用的函数；add
esp, 0C 调用方“平衡”栈指针 esp （释放栈上的参数）；因为对于 C 调用约定，函数没有清理参数，当函数返回时，所有参数位于实际 stack （逻辑上）的顶部位置。也就是说，在 C 调用约定中，被调用函数的参数的生命周期，全权由调用方负责。（被调用方不负责参数的内存管理）。因此，类似 printf 这种具有可变个数的参数的函数，都是 c 调用约定。（因为这种情况下，只有调用方知道参数的实际数量，而被调用的函数无法提前知晓）。在 __stdcall ( 大部分 windows api 函数）调用约定中，被调用的函数的参数的生命周期，相当于双方各承担一部分，调用方负责分配，被调用方负责回收。被调用函数通过 ret n 返回。（n 是返回后令 esp 增加的偏移值，也就是参数占用的空间大小）。stack frame 之间间隔是 stack 上函数的返回地址。
在 DEMO 的截图中，画出了调用深度最大时的 stack frames。当函数采用 EBP 作为 stackframe 基准指针时，也就是说函数采用如下的开头：mov
ebp, esp然后可以用 ebp 到高地址方向取函数参数。例如：对于 x86 目标平台的程序（WIN32）（指针和 stack unit 尺寸是 4 bytes），则：函数的第一个（函数声明时最左侧）的参数是 [ ebp + 8 ]；第二个参数是 [ebp +
C h];第三个参数是 [ebp + 10 h];第四个参数是 [ebp + 14 h];。。。EBP 的低地址方向，是为函数的临时变量分配的空间。从 EBP - 4 位置开始。当然如果程序用 release 配置编译，可能函数不会使用 ebp 作为基准指针，而是直接用 esp 来定位参数和临时变量，由于 esp 随着函数调用在动态变化过程中，所以汇编代码可读性要比采用 ebp 作为基准的汇编代码【差】的多。在本例中，可以看到函数调用关系：main -& fact ( 4 ) -& fact( 3 ) -& fact( 2 ) -& fact ( 1 )然后依次返回。回到网友关心的问题，那么 fact 函数的返回值去了哪里？就这个例子来说，fact (1) 的返回值，被存储到 fact (2) 中的 x，fact (2) 的返回值，被存储到 fact (3) 中的 x，...fact (4) 的返回值，被存储到 main 中的 y。因此，虽然 fact 函数代码只有一份，但是在递归调用时，fact 的 stack frame 可以在栈上存在多份。每次调用 fact，它都有独立的 x 被分配在栈上。因此，依次 fact (4)，fact (3), ..., fact (1) 时，它们同时出现在栈上，且彼此是独立的，它们的地址不同。-------------------------------------------------------------------------------------------------备注：DEMO 中演示的 C 源码如下（每行起始位置的数字是代码行号）：04 | int fact(int n)
x = fact(n - 1);
return (n + x) * 2;
16 | int _tmain(int argc, _TCHAR* argv[])
int y = fact(4);
printf("y = %d;\n", y);
DEMO 中模拟运行的汇编代码如下（每一步模拟运行的汇编代码显示在 DEMO 的状态栏中）：这些汇编代码，参考了以上 C++ 代码用 VC2005 debug 配置的编译结果。在 DEMO 中只能在状态栏中看到当前的指令。在这里列出被模拟执行的汇编代码的全貌。如果你读懂了下面的汇编代码，大概也就不会觉得【递归函数】相对于【普通函数】有什么特别的了。（底层视角，根本就不在意不关心函数是否是递归的）。以下汇编代码的位于行首起始位置的指令地址（即指令在代码段中的虚拟地址），是经过我处理后的“伪指令地址”，由两部分（每部分都是一个数字）构成，第一个数字表示该指令对应的高级语言（C语言）代码的行号，第二个数字表示该指令在由该行高级语言代码所编译成的多条指令中的序号。例如：07.2 jle 13.1表示这条指令是前面的 C 语言代码的第 7 行 "if (n & 1)" 所编译指令中的第二条。; fact:
var_x = dword ptr -4
arg_n = dword ptr 8
06.1 push ebp
06.2 mov ebp, esp
06.3 sub esp, 4
; alloc var_x;
07.1 cmp [ebp+arg_n], 1
; compare arg_n with 1;
07.2 jle 13.1
09.1 mov eax, [ebp+arg_n]
09.2 sub eax, 1
09.3 push eax
; push n - 1;
09.4 call 06.1
; call fact(n - 1);
09.5 add esp, 4
09.6 mov [ebp+var_x], eax
; x = fact(n - 1);
10.1 mov eax, [ebp+arg_n]
10.2 add eax, [ebp+var_x]
; eax = n +
10.3 shl eax, 1
; eax = (n + x) * 2;
10.4 add esp, 4
10.5 pop ebp
; return (n + x) * 2;
13.1 mov eax, 1
13.2 add esp, 4
13.3 pop ebp
; return 1;
var_y = dword ptr -4
18.1 push ebp
18.2 mov ebp, esp
18.3 sub esp, 4
; alloc var_y;
18.4 push 4
18.5 call 06.1
; call fact(4);
18.6 add esp, 4
18.7 mov [ebp+var_y], eax
; y=fact(4);
19.1 push eax
19.2 push _format
; push addr of:"y=%d;\n";
19.3 call printf
19.4 add esp, 8
20.1 mov eax, 0
; return 0;
20.2 add esp, 4
; free var_y;
20.3 pop ebp
; 模拟 printf 的伪指令
----好了，最后是思考时间，下面的问题留给大家思考：（1）对于本例中的 fact 函数（以下简称 f ），如果有函数 main 调用了 f ( k )， 且 f 调用自身也算作一次。请问 f 一共被调用多少次？（2）请问 f (5) 中的 x 的地址，和 f (3) 中的 x 的地址，谁大谁小？（3）已知有下面的函数：void foo(char b1, double f2, char b3, char b4)
printf("%d\n", (char*)&b4 - (char*)&b1);
在 X86 （WIN32）架构计算机上未经过优化（例如 debug 版本）的输出是什么？----PS：（1）以前辅导一个学妹，其课程要求用 raptor 这种流程图软件，来编写一些简单的程序。大多数情况下，都是简单的。（当然我个人不理解学这个东西有啥帮助。感觉还不如直接学编程呢。）其中有编写斐波那契数的递归函数的题目。但是由于 raptor 很奇葩的是，不支持向 sub graph （相当于函数）传递参数，要传递信息，只能用全局变量。这种限制，使得要用 raptor 模拟出递归函数具有很大难度，必须要掌握底层函数调用的过程，因此这反而成了初学者不可能完成的任务，所以要模拟递归函数，就需要特殊方法。为此，我用一个全局变量 （i ）跟踪调用深度，用全局数组来模拟递归函数调用时的临时变量和参数。通过控制这个调用深度，来模拟控制递归函数的调用过程。这是用 raptor 模拟的递归函数的结果：------（2）这是前些天遇到一个学生寻求该算法的帮助，我写的另一个（中国象棋中的）马 踏（国际象棋的）棋盘的演示程序，把算法求解过程，用可视化的方式（也是一种动画形式）展示出来（每个 cell 周围的 8 个梯形的颜色代表了算法对该方向子节点的处理结果），马不重复的走遍 8x8 棋盘的每个格子的算法（算法采用贪心法+回溯法），求解过程是搜索一个 8 叉树，网上的算法代码采用的是递归函数，被我改写成非递归函数，（根据对方的反馈）这也使得即使采用的算法完全相同的情况下，非递归版本的也比递归版本的速度提高了，我说，这是因为递归函数比非递归版本多了很多次函数调用，尽管函数调用通常不会成为影响性能的关键点，但较大数量积累起来，这就造成了一定时间成本：其可执行文件的下载链接：9514 条评论分享收藏感谢收起162 条评论分享收藏感谢收起}