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

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

回复 80 楼:
Dennis M. Ritchie 的博士论文:
Computational Complexity and Program Structure, May 15 1967
www[dot]cs[dot]cornell[dot]edu/courses/cs6110/2012sp/MeyerAndRitchie-67[dot]pdf

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

#include <stdio.h>
#include <time.h>
#include <vector>
using namespace std;
int fib_r(int n) {
    if (n <= 1) return n;
    return fib_r(n-2) + fib_r(n-1);
}
template<class T>
class Array {
public:
    Array() {
        top = -1;
    }
    void push_back(const T& v) {
        arr[++top] = v;
    }
    T& back() {
        return arr[top];
    }
    void pop_back() {
        --top;
    }
    bool empty() {
        return top == -1;
    }
private:
    T arr[200];
    int top;
};
typedef struct STATEDATA {
    // param
    int n;
    // data
    int state; // 调用状态
    int ret1; // 记录第一次返回值
    STATEDATA(int param1 = 0)
        :n(param1), state(0) {}
}STATEDATA;
int fib(int n) {
    int eax = 0; // 返回值（eax寄存器）
    Array<STATEDATA> state; // 递归栈状态
    state.push_back(STATEDATA(n)); // call fib(n)
    while (!state.empty()) {
        int n = state.back().n;
        ++state.back().state;
        if (n <= 1) {  // 递归出口
            eax = n;
            state.pop_back(); // return


        } else {
            switch (state.back().state) {
            case 1:
                state.push_back(STATEDATA(n-1)); // call fib(n-1)
                break;
            case 2:
                state.back().ret1 = eax;
                state.push_back(STATEDATA(n-2)); // call fib(n-2)
                break;
            default:
                eax = eax + state.back().ret1;
                state.pop_back(); // return
            }
        }
    }
    return eax;
}
int main() {
    int n;
    while (scanf("%d", &n) !=EOF) {
        clock_t t = clock(), t1, t2;
        printf("%d\n", fib(n));
        t1 = clock();
   

        printf("%d\n", fib_r(n));
        t2 = clock();
        printf("Time %ld %ld\n", t1 - t, t2 - t1);
    }
    return 0;
}
fib两个实现版

欢迎炮姐
炮姐给出了 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 的意思了~

接下来是 stack_push 和判空

接下来是 stack_pop 弹栈 和 stack_top 查看栈顶元素：

嗯, 完毕。
后续使用这个接口来说明一般式

销毁栈的接口实际上还有个问题.
正常的实现应该
node_t **cur = &thiz->top;
node_t *tmp;
while (*cur)
{
　　tmp = *cur;
　　cur = &(*cur)->next;
　　if (thiz->des)
　　　　thiz->des(tmp->data);
　　free(tmp->data);
　　free(tmp);
}
thiz->top = NULL;
free(thiz);
......o(）＾）)o 唉

ok. 栈ADT的实现对于一般式的说明来说实际上无关紧要. 能用就行.
======================================================
那么接下来就是一般式的说明了.
======================================================