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

@ RichSelian
@ 御坂美琴みさか
@ 顶之座__赫卡特

怎么感觉不太对劲，叔叔不会用@么...

算了, 开始先。
是一篇非常长的基础教学贴。由于完整性/清晰性保证，以及完成度保证，完成本帖的时间会非常长，大约需要一周(LZ白天有事情，见谅)。请勿插楼。

OK, 回到主题，言归正传。
请注意，是任意形式的递归，是化解的一般式。
通过学习这个一般式，学习完毕之后，任意复杂的递归式，要将其化解为栈处理，只需要按照死步骤一步一步做就可以了 -- 当然，LZ这里说的是，该怎么样去写代码，因为它最简单直白。怎么样，如果还不会这个一般式，或者，在做类似的事情时总有些感觉吃力，那么它听起来是不是还是有一点儿诱惑力的，呵呵。
为了不对新手造成误导，这里有必要澄清本帖的主题。主题所谓的“递归调用化解为栈处理”，意思是，将递归函数调用化解为“一个由stack_push stack_pop stack_top等函数调用组成的循环式子”。这里的 stack_push, stack_pop, stack_top是指，程序员自己实现的一个ADT(Abstract Data Type)中的函数操作接口，这个ADT叫做栈。
要知道，在C语言中，函数调用链本身就是栈处理的，处理C语言中函数调用链的是进程栈/线程栈，进程栈/线程栈是一个C语言程序运行环境的必备部件。
将递归调用化解为栈处理的意义在于，大多数计算机系统，对进程栈/线程栈的大小都是有限制的。譬如在Linux系统上，进程栈的大小限制大约是10MB. 因此，如果程序员直接使用进程栈来进行递归调用, 有可能耗尽进程栈空间，导致 Segment Fault. 虽然进程栈的大小是可调整的；然而程序员最好不要做这样的假设；因此，将递归调用化解到一般位于堆(Heap)上的ADT栈上, 在某些场合也许非常有必要。
更为苛刻的是，比如Linux内核，每个进程的内核栈大小只有1 - 2页，每页只有4 / 8KB, 也就是最多只有16KB的内核栈；假设程序员在编制一个驱动程序；这个驱动程序如果耗尽了内核栈 -- 呵呵，结果嘛...
============> 阅读本帖的童鞋, 请注意!!!
读到这里，如果你还是没有明白本帖的主题是指什么，或者你不知道什么是进程/线程栈，或者你不清楚如何实现一个叫做栈的ADT(Abstract Data Type, 抽象数据类型, 数据结构中讲授的内容)，那么，你非常非常不适合阅读这篇文章，这篇文章可能会对你造成概念上的混淆什么的。
===》因此，LZ要在这里劝退你，等你有了足够的基础知识之后再来阅读。如果你具备了足够的基础知识，而且你正好对于本帖主题的问题有所迷惑，那么欢迎你，LZ向你推荐本文(稍微有点那啥卖瓜的味道，呵呵).
[当然, 本帖讨论的语境限于C语言, 因此，
1. 请勿将
-- LisP Like的, prolog like的, ...
-- 或者所有functional programming paradigm, declarative paradigm的...东西乱入；
-- 甚至, C++ -- LZ个人口味上只是喜欢C, 对C++不是很感冒.
2. 并避免
-- corutine, continuation之类的东西；
理由: 1, 这些都不是C语言所具备的特性；2, LZ想要限定场景和语境以明确讨论主体]。

=========================> 分割线 <=========================
首先，“任意递归都可以化解为栈处理”是一个一般结论，是有理论依据的，并可能/应该被形式化地证明过。请自行度娘Dijkstra, 我们这个时代最伟大的计算机科学家之一。在此，LZ引用一段，如下：
“最早提出用栈（stack）来编译复杂公式的是德国的Bauer和Samelson，他们的著名论文‘顺序公式的翻译’（Sequential Formula Translation）是编译方面的经典论文。最近有些报道说Dijkstra是栈的发明人，这恐怕不符事实。Dijkstra发展了栈的概念，使之用于整个编译，以及目标代码运行时的动态存储分配，并在此基础上和Jenson完成了世界上第一个ALGOL60编译系统，采用了他首创的优先数编译算法。其中递归调用子程序时的环境维护是Dijkstra的重要贡献，Display这一术语就是当时他发明的，这是用来维护动态环境的一组寄存器（软件），其结构清晰并能适应任何复杂情况。”

=========================> 分割线 <=========================
LZ发本文的契机。
确实可以找到许许多多资料，告诉你，怎么将递归调用化解为栈处理，然后举一两个例子说明。然而非常可惜的是，LZ发现，大多数文章都非常无聊，甚至有的连作者本人的理解都可以说是有问题的。在这些文章中，作者会说，这比较简单，BLABLABLA，... 但是他们从来没有给你总结过一般式 -- 对，几年前我学习数据结构时，就是这样的。如果没有一般式[就是说，通过这种方法，总能够...呵呵。数学家很喜欢用：对于任意xx, 必然存在xx, 使得xxx成立，哈哈]，那么怎么能够证明 -- “所有递归都可以化解为栈处理”？
所以LZ我怒了。那时的LZ非常菜B，加之天资愚钝，所以过了大约一个多月才大彻大悟 -- 就是说，LZ自己总结出了一套一般式。
因为LZ不小心喝了点儿咖啡睡不着了，需要做点事情来打发这漫漫长夜，于是，本文就开始了。
虽然本文的主题非常简单明了, 但是为了阐明本主题, 实际上需要较多的基础铺垫. 因此本帖短时间内估计无法完结, 这里我只是一时兴起先起个头... 要填这坑，倒也不是太easy...
o(）＾）)o 唉... 既然坑都挖了， 那么LZ肯定会填完的，童鞋们，勿要插楼啊。

唔。
为了不要满嘴跑火车，看来LZ还是必须要准备个提纲了。
提纲如下。
1. 递归. 定义, 阐述.
2. 进程栈/线程栈, 阐述.
3. 递归的形式, 阐述, 实例. 会有Hanoi Tower哦!
4. 一个基本的链表/动态数组数据结构/容器实现[只会选一种], 用于作为栈ADT实现的基础
5. 栈ADT实现, 阐述
6. 一般式, 阐述, pseudo code, C like
实例，Hanoi Tower again.
7. 应用1：AVL树
8. 应用2：递归下降分析法实现的最简四则运算器, 及其化解
=========================> 分割线 <=========================
Damn it...
不知不觉就列出这些了... 坑真的大了... 什么时候才填完呢...

先休息去了。
LZ这两天有事情，三天后必来填坑。

等待更新中……

正在期待......

守着