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

@ 良化纲领_
对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此文确实对童鞋们有帮助，则甚好。
######################

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

=========================> 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, 但毫无疑问是没有机会等待这个程序执行完毕了.
================================================================

=========================> Chapter 3 <=========================
C语言中递归的形式
===============================================================
结语
===============================================================
关于[C语言中, 以后文中不明确指明时都指这个]递归的形式, 到这里就结束了.
LZ根据三个例程[都是递归中最简单的, 只是Hanoi Tower稍微困难], 说明了递归的形式.
实际上, 核心内容只有一点:
通过画递归树分析递归, 确定执行路径和栈深.
基本上这些步骤做下来, 分析C语言的递归函数时就可以畅行无阻了. 可以直接在头脑中构建较浅的递归树, 这样在直观上和心算能力上都会有一定程度的提升. 递归树使我们可以毫无差错地手工计算任意函数的中间状态而不需要感到清晰性的缺失 -- 当怀疑某个递归是否正确的时候 -- 画递归树.
===============================================================

通过 Section 3 的讲解,
分析递归执行路径之类的基础问题是足够了.
有一类涉及递归的实例应该再介绍一些, 比如排列计数之类的.
但是如果一直介绍递归实例也不好. 毕竟本帖的主题主要还是关于如何将递归从 系统栈 转移到 ADT栈 处理的.
================================
所以, LZ还是先写转移处理的一般式, 然后再视情况加码内容.
当然, 树的内容和最简四则计算器还是有的. 是不是完整地实现一个AVL树, LZ可能会视情况决定, 因为递归主要是树的深度遍历相关的.
LZ应该还会给出一个简单的矩阵实现的稀疏图的深度优先遍历.
================================
此帖坑又深了些, 但是填坑较慢, 这个木办法的事情~~~ 最近手上要处理的事情实在有点多.
================================

欢迎炮姐
炮姐给出了 fibonacci 数列从系统栈上搬到ADT栈上的处理方式.
实际上, 炮姐给出的就是一般式，乃们要根据这个例子多学习。
LZ接下来实现渣ADT栈，并说明一般式。

首先是
list_stack.h
这个声明了ADT栈的接口.
结构非常简单，node_t 是链表节点，stack_t 就是栈 ADT 的基本结构了.
这里也不把操作写在结构体内部了, C实现就是要够简单.

上面的实现中声明了一个 stack_op 的函数指针类型.
这个函数指针用来在销毁栈[假设此时栈未弹空]时，回调用户的销毁函数，防止内存泄漏。
什么意思呢? 因为每个栈帧在这个链栈中表现为一个链表的节点。节点中的 void *data即用来存放用户数据的指针。 该指针指向的内存是 ADT 实现中分配的，就是说用来存放用户数据的副本。 问题在于，实现 ADT 时我们不知道用户会存放什么样的数据。假设用户存放的数据中还有一个指针[即 void *data指向的那片内存中，还有一个指针]，这个指针又指向用户自己分配的内存， 则我们在释放 void *data指向的那片内存之前， 还得把用户分配的内存释放掉。
但是我们又不知道该怎么释放，因为毕竟void *data指向的内存内容对于实现 ADT 时的我们来说是未知的。 因此用一个函数指针回调用户的销毁函数来释放。
前面已经说过，这个栈由于链表实现的原因，很慢。LZ没有具体测试，不过比系统栈慢上百倍是正常的~
下面看实现~
============================================================

list_stack.c
首先是stack_create 和 stack_destroy, 创建栈和销毁栈~:

注意, 简单起见, list_stack.h 和 list_stack.c 是放在同一目录的。
因此LZ包含头文件时直接用的 #include ""
如果用 #include <>, 则需要在编译时指定头文件所在目录~ gcc指定头文件搜索目录的选项是 -I
也可以写个简单的 Makefile. 不过简单起见就算了.

上面的创建栈接口的两个参数说一下~
ele_size 用于指定每次压栈/弹栈时用户数据占用内存大小, 我们让它是固定的.
des 是回调销毁函数的指针. 如果用户数据中没有指针, 那么调用时给成NULL即可.
看销毁栈的接口, 就知道 des 的意思了~