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

=========================> Chapter 3 <=========================
C语言中递归的形式
===============================================================

=========================> Chapter 3 <=========================
C语言中递归的形式
===============================================================
章首言
===============================================================
关于递归的形式，需要一些基本的分析和综合，或者说需要一些洞察。
这正是解决任何一个问题的基本方法，首先分析该问题的表现形式，是否能够穷尽它的表现形式，然后开始综合，抽象出一般的结论。
前述已经提及，C语言中的递归只限于有终止的递归。
这里直接给出结论先，然后开始一些实例，最后重复该结论。
1. 递归的形式分类
1). C语言中的递归首先分为直接的递归和间接的递归。
所谓直接递归，就是函数foo实现中直接调用foo. 所谓间接递归, 就是函数foo实现中不直接调用foo, 而是调用函数bar, 但是函数bar又调用函数foo.
2). 直接的递归分为线形的递归和树形的递归[也称单路递归和多路递归]。
所谓线形的递归，是指函数foo的实现中，只调用它自身一次。
所谓树形的递归，是指函数foo的实现中，调用它自身多次。
3). 根据递归调用是否出现在函数尾部, 将递归分为尾递归和非尾递归。
2. 关于递归的结论
1). 所有间接递归都可以化解为直接递归。
这个洞察是很简单的, 但需要到最后才给出一个实例。
2). 所有尾递归都可以直接化解为迭代处理，不需要用栈。
3). 所有递归都可以用栈处理
这是显然的，前面已经非形式化地证明过，递归就是栈处理的。
4). 并非所有递归都可以化解为迭代处理[这里的迭代处理是指, 不使用栈的迭代]。
这某种程度上显然的, 因为递归的本质是栈处理的。然而形式化或者非形式化地证明它却可能相当困难，所以LZ只是给出这个结论，有兴趣做证明的不妨自己动手。
===============================================================

=========================> Chapter 3 <=========================
C语言中递归的形式
===============================================================
Section 3.1
===============================================================
本节通过一个极致简单的实例介绍关于线形递归的两个基本认知。因为线形递归是除了尾递归之外最简单的递归。
该实例是一个简单的求和实例，即：求 1 + 2 + 3 + ... + n.
这不明明是一个循环可以搞定的事情吗? 嗯... 先别管这个。
如果使用递归定义上述求和序列，那么很显然递推规则如下：
f(n) = f(n - 1) + n
还需要一个基础情形/终止条件. 这个终止条件是
f(1) = 1
或者
f(0) = 0
于是，这个求和的递归是这样的(简单起见, 略过了很多东西, 比如负数会导致...):
/********************************************************************/
#include <stdio.h>
int sum(int n)
{
// addr0, function instructions start address, 函数起始处指令地址
____int tmp;
// stop condition, 终止条件
____if (n == 1)
____{
________printf("这是第 %d 层返回.\n", n);
________return 1;
____}
____printf("这是第 %d 层调用.\n", n);
// addr1, calling point / point of invocation addr, 递归调用点指令地址
____tmp = sum(n - 1) + n;
____printf("这是第 %d 层返回.\n", n);
// addr2, function instructions end addr, 函数结束处指令地址
____return tmp;
}
int main(void)
{
____int n;
____printf("pls input a num:");
____scanf("%d", &n);
____printf("求和的结果是：%d\n", sum(n));
____return 0;
}
/********************************************************************/
这个递归是可以直接写成尾递归的. 即, 不需要定义临时变量tmp, 直接在最后写上
return sum(n - 1) + n;
LZ之所以没有写成尾递归, 是为了能够清楚地观察到递归执行的路径。
比如输入5，
这个程序的输出将会是：
这是第 5 层调用.
这是第 4 层调用.
这是第 3 层调用.
这是第 2 层调用.
这是第 1 层返回.
这是第 2 层返回.
这是第 3 层返回.
这是第 4 层返回.
这是第 5 层返回.
求和的结果是: 15
===============================
1. 第一个简单的结论是，终止条件必须写在递归调用点之前。
这是显然的，否则递归调用永远不会终止。
2. 第二个简单的结论是，如果把递归调用点之前的代码序列称之为递归函数的上半部，把递归调用点之后的代码序列称之为递归函数的下半部，那么递归函数的执行一定要让上半部的所有代码序列全部执行完毕(直到遇到终止条件)才能够执行下半部的代码序列。
注意我在代码中标记了注释。
addr0 -- addr1是该递归函数的上半部。
addr1[之后] -- add2 是该递归函数的下半部。
也即，每次调用，进去之后从函数开始指令执行。执行下去，又遇到函数调用。于是又从函数开始指令执行。又遇到函数调用，... 直到终止条件。此时返回。返回到哪里？由于原调用方的上半部已经执行。所以开始执行原调用方的下半部。原调用方下半部执行完，返回到原调用方的原调用方, 执行其下半部。返回， ...
===============================
如果是树形递归呢？先不管，这两个简单结论先放着。
===============================
==============================================================
下面，画该递归调用的栈帧建立和销毁过程。

首先，可以观察到该函数中只有两个局部变量，一个是参数n, 一个是局部变量tmp。由于调用方[caller]需要将返回地址也传到被调用方[callee]，所以实际上还有一个返回地址pc[Program Counter].
于是，该函数的栈帧布局[箱子布局]如图所示：
|#################|
|+++ para, n +++++| ##### 这个盒子用来装参数
|-----------------|
|+++ Caller_PC +++| ##### 这个盒子用来装返回到调用方的地址
|-----------------|
|+ auto var, tmp +| ##### 这个盒子用来装自己的局部变量
|#################|
如果我们把上面这个栈帧[箱子]再画得简单点，并忽略掉返回地址，那么这个栈帧的简约画法如下:
|#################|
|+++++++ n +++++++|
|-----------------|
|++++++ tmp ++++++|
|#################|
再简单点，极致简单：
|#################|
|++++ n, tmp +++++|
|#################|
=======================================
调用时栈帧被相继建立，于是：

********************** ** main ==> sum(5) // main函数调用sum(5), sum(5)栈帧建立
|#################|*** +++此时, n的值/状态确定了[因为它是传进来的参数!],
|++++ n, tmp +++++|*** +++但tmp的状态还不确定
|#################|*** ** sum(5) ==> sum(4) // sum(4) 栈帧建立
|++++ n, tmp +++++|*** +++同理, sum(4)知道n的状态, 但还不确定tmp的状态
|#################|*** ** sum(4) ==> sum(3)
|++++ n, tmp +++++|***
|#################|*** ** sum(3) ==> sum(2)
|++++ n, tmp +++++|***
|#################|*** ** sum(2) ==> sum(1)
|++++ n, tmp +++++|***
|#################|*** ** sum(1)
|++++ n, tmp +++++|*** +++此时, sum(1)直接返回1.
|#################|***
接下来, 返回：
sum(1) ==> sum(2) ==> sum(3) ==> sum(4) ==> sum(5) ==> main
+++++++==> sum(2)中tmp的值/状态确定了.
+++++++++++同时, sum(1)栈帧被销毁.
+++++++++++++++++==> sum(3)中tmp的值/状态确定了.
+++++++++++++++++++++同时, sum(2)栈帧被销毁.
+++++++++++++++++++++++++++++==> sum(4)中tmp的值/状态确定了.
+++++++++++++++++++++++++++++++++同时, sum(3)栈帧被销毁.
++++++++++++++++++++++++++++++++++++++++==> sum(5)中tmp的值/状态确定了.
++++++++++++++++++++++++++++++++++++++++++++同时, sum(4)栈帧被销毁.
+++++++++++++++++++++++++++++++++++++++++++++++++++==> 返回tmp到main函数
+++++++++++++++++++++++++++++++++++++++++++++++++++同时, sum(5)栈帧被销毁.
===============================================================
综上. 本节通过一个简单的例子观察了线形递归的执行步骤，并画出了栈帧建立和
销毁的过程。
所有的一切，都从理解这个例子开始。
===============================================================
#### 以后继续。字符画真难画啊。另外代码都是下划线做缩进，对度娘，LZ是很无奈的。

帖子回来了?..

=========================> Chapter 3 <=========================
C语言中递归的形式
===============================================================
Section 3.2 最简单的树形递归 Hanoi Tower
===============================================================

留

不明觉厉

大叔 ，关于新手学习数据结构有没有啥建议啊 ？

牛逼啊,楼主

我实验的结果是我自己拆递归后，比原来的递归写法运行速度更慢，难道我写渣了？

=========================> Chapter 3 <=========================
C语言中递归的形式
===============================================================
Section 3.2.2 又一个树形递归的例子 Hanoi Tower
===============================================================
接上.
如果已经写过汉诺塔, 那么写出来是很容易的.
但是假设从来没有写过汉诺塔，那么应该怎么考虑这个问题呢？
没错, 我们已经得到了递推公式, 但是这个递推公式只是关于移动次数的, 对我们如何写程序没有太多帮助, 因为我们的程序要求将移动的步骤全部输出.
然而, 得到递推公式的思考过程仍然是有用的, 要移动n个碟子[from A to C], 我们需要三步:
1). 移动上面 n - 1 个碟子, from A to B.
2). 移动最底下的 1 个碟子, from A to C.
3). 移动 n - 1 个碟子, from B to C.
我们发现, 移动 n - 1 个碟子和移动 n 个碟子是完全一样的问题[Recurrent Problem]. 于是, 这三个步骤就成为了重复的过程, 于是这重复的过程[Recurrent Procedure/Process]正是将递归函数抽象出来的关键.
/*************************************************************/
#include <stdio.h>
void hanoi(int n, char A, char B, char C)
{
　　if (n == 1)
　　{
　　　　// move 1 disk.
　　　　printf(" %c ===> %c \n", A, C);
　　}
　　else
　　{
　　　　// first, move n - 1 disks from A to B
　　　　hanoi(n - 1, A, C, B);
　　　　// then, move 1 disk from A to C
　　　　hanoi(1, A, B, C);
　　　　// at last, move n - 1 disks from B to C
　　　　hanoi(n - 1, B, A, C);
　　}
}
int main(void)
{
　　int n;
　　printf("pls input disk nums:");
　　scanf("%d", &n);
　　printf("now, start move......\n");
　　hanoi(n, 'A', 'B', 'C');
　　return 0;
}
/*************************************************************/
汉诺塔的递归树[移动3个碟子]如下, 每个节点有三个孩子, 执行路径像fibonacci数列一样画. 这里没有画出来. 另外由于'A','B','C'占用太宽, 所以就将其表示成ABC了.
　　　　　　　　　　　　　　　　　hanoi(3,ABC)
　　　　　　　hanoi(2,ACB) 　　　hanoi(1,ABC) 　　hanoi(2,BAC)
　　　　　　　　　　　　　　　　　A ==> C
hanoi(1,ABC) hanoi(1,ACB) hanoi(1,CAB)　　hanoi(1,BCA) hanoi(1,BAC) hanoi(1,ABC)
A ==> C　　　A ==> B　　　C ==> B　　　　 B ==> A　　　B ==> C　　　A ==> C
移动3个碟子是 2 ^ 3 - 1步, 移动四个碟子需要2 ^ 4 - 1共15步, 四个的画不下.
所以测试的时候 n 不要输入太大, 3或者4就可以了, 验证起来简单. 如果输入64, 由于递归的最大栈深只有64个栈桢, 因此绝不会因栈溢出而导致程序dump, 但毫无疑问是没有机会等待这个程序执行完毕了.
================================================================