c语言吧 关注：801,793贴子：4,376,120
不感兴趣
开通SVIP免广告
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这一术语就是当时他发明的，这是用来维护动态环境的一组寄存器（软件），其结构清晰并能适应任何复杂情况。”
首先，“任意递归都可以化解为栈处理”是一个一般结论，是有理论依据的，并可能/应该被形式化地证明过。请自行度娘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...
不知不觉就列出这些了... 坑真的大了... 什么时候才填完呢...
不感兴趣
开通SVIP免广告
LZ回来了.
=========================> Chapter 1 <=========================
递归的定义和阐述
1.1. 广义的递归, 其定义/概念/阐述
“Recursion is the process of repeating items in a self-similar way. ”
递归是指以自相似方式重复事物的过程。(请自行抽出key, 递归是过程)
这里唯一要注意的, 广义的递归是一种过程，这种过程，亦是一种刻画/描述/理解现实世界中许多事物的一种方法/方式。它可以是无限无终止的。
有趣的比如说GNU. GNU的定义是 GNU is not Unix.
GNU -> GNU is not Unix, 如果把GNU当成变量(非终结符), 把is, not, Unix都当做终结符, 把GNU -> GNU is not Unix称之为产生式, 产生式左边的GNU作为这个产生式的头部, 产生式右边的GNU is not Unix称之为产生式体, 那么，GUN -> GNU is not Unix 就是一个上下文无关文法(Context-Free Grammar). 对该文法的推导[文法推导即替换]如下：
GNU ==> GNU is not Unix
==> GNU is not Unix is not Unix
==> GNU is not Unix is not Unix is not Unix
....
这是一个无限无终止的左递归(即，该文法产生式体之最左为非终结符/变元)。相应的，非终结符/变元出现在文法最右的文法称之为右递归。这里的“左递归”，“右递归”中的“递归”，是广义的递归。
=========================> Chapter 1 <=========================
递归的定义和阐述
1.1. 广义的递归, 其定义/概念/阐述
“Recursion is the process of repeating items in a self-similar way. ”
递归是指以自相似方式重复事物的过程。(请自行抽出key, 递归是过程)
这里唯一要注意的, 广义的递归是一种过程，这种过程，亦是一种刻画/描述/理解现实世界中许多事物的一种方法/方式。它可以是无限无终止的。
有趣的比如说GNU. GNU的定义是 GNU is not Unix.
GNU -> GNU is not Unix, 如果把GNU当成变量(非终结符), 把is, not, Unix都当做终结符, 把GNU -> GNU is not Unix称之为产生式, 产生式左边的GNU作为这个产生式的头部, 产生式右边的GNU is not Unix称之为产生式体, 那么，GUN -> GNU is not Unix 就是一个上下文无关文法(Context-Free Grammar). 对该文法的推导[文法推导即替换]如下：
GNU ==> GNU is not Unix
==> GNU is not Unix is not Unix
==> GNU is not Unix is not Unix is not Unix
....
这是一个无限无终止的左递归(即，该文法产生式体之最左为非终结符/变元)。相应的，非终结符/变元出现在文法最右的文法称之为右递归。这里的“左递归”，“右递归”中的“递归”，是广义的递归。
=========================> 分割线 <=========================
1.2. Formal definitions of recursion
递归的形式化定义
In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties:
1). A simple base case (or cases), and
2). A set of rules which reduce all other cases toward the base case.
数学/计算机科学中, 如果一类对象/方法的定义具有如下两个特性/属性[properties], 那么它就是递归的。
1). 基准情形/简单情形,
2). 一组能够将所有情形规约/递推[reduce]至基准情形的规则. 注意了. 这里的形式化定义，已经不再是广义的递归了。就是说它要求递归是可以终止的。没错，要讲的 C语言的递归函数调用，应该归结为这样的一类递归。
1.2. Formal definitions of recursion
递归的形式化定义
In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties:
1). A simple base case (or cases), and
2). A set of rules which reduce all other cases toward the base case.
数学/计算机科学中, 如果一类对象/方法的定义具有如下两个特性/属性[properties], 那么它就是递归的。
1). 基准情形/简单情形,
2). 一组能够将所有情形规约/递推[reduce]至基准情形的规则. 注意了. 这里的形式化定义，已经不再是广义的递归了。就是说它要求递归是可以终止的。没错，要讲的 C语言的递归函数调用，应该归结为这样的一类递归。
=========================> 分割线 <=========================
---------------------------------------------------------------------
再扯两句。我们看到了“形式化[Formal]”这个词。请问，什么是形式化的，什么是非形式化[Informal] 的？一般来说, 建立一个系统的方式, 是先有定义和公理, 然后根据定义和公理, 推导各种引理和定理, 然后 -- 一个系统就建立起来了. 比如欧氏几何, 通过有限的公理和公设, 去证明《几何原本》中的所有"真命题". 这估计是人类史上最早的形式化地建立系统的例子, 这个系统的基础是有限的公理和公设, 然后整个系统就是 -- 欧几里得几何, 也即几何原本. 那么欧氏几何就是形式化的.
由于近代符号逻辑的发展, 形式化(formal methods)一般被纳入符号逻辑/命题逻辑/数理逻辑的数学分支中去了. 不过要注意, 形式化只是一种思考方式, 也就是说形式化方法的本质就像前述说欧氏几何的建立一样. 只不过, 由于数学家们认为, 将这种思考方式符号化从某种程度上有助于思考本身(布尔代数奠基人, 其有一本书的名字就是《The Laws of Thought》). 于是, 在数学上看来, 形式化地建立一个系统需要:
Formal systems in mathematics consist of the following elements:
A finite set of symbols (i.e. the alphabet), that can be used for constructing formulas (i.e. finite strings of symbols).
A grammar, which tells how well-formed formulas (abbreviated wff) are constructed out of the symbols in the alphabet. It is usually required that there be a decision procedure for deciding whether a formula is well formed or not.
A set of axioms or axiom schemata: each axiom must be a wff.
A set of inference rules.
即:
1. 一组有限的符号**, **中的符号用来构建公式. [比如, 令命题p表示"3 + 2 = 5", p就是一个符号, 代表一个命题. 比如, 对两个命题的合取一般表示为 p ^ q, 即, p成立而且q也成立, 就像 C语言中, &&对两个表达式取逻辑乘一样. 对两个命题的析取一般表示为p v q, 即p成立, 或者q成立, 或者二者皆成立]
2. 语法规则, 就是根据符号**(亦称字母表)构建合式公式(原文中的well-formed formulas, 一般数理逻辑中译为合式公式)的规则. [合式公式是由命题常项、命题变项、联结词、括号等组成的符号串, 但不是由这些符号任意组成的符号串都是合式公式]. 语法规则用于判断一个公式是不是合式公式.
3. 一组公理或者公设. 公理和公设必须是合式公式.
4. 一组推理规则.[_三-段-论_神马的]. 即, 形式化方法的本质仍然是: 根据基本的公理和公设, 加上一组推理规则, 然后... 建立整个系统. 就是这个意思. 形式化的方式和别的方式的本质区别在于, 是不是具有有限的基本模型抽象, 然后根据这些基本模型抽象推导出/建立整个系统模型. 对于形式化的方式来说, 由于这种形式化的方式保证了逻辑上的严格性, 在系统日益复杂的情况下, 有可能思考需要回到某个定义本身开始. 因此这种方式被广泛地应用.
***************************************
那么非形式化的方式是什么？就是直观地描述. 如果一上来就给人一套数学形式化描述的东西, 然后让人根据这个东西去推导什么的, 谁都会发疯的. 于是一般在介绍一个形式化的定义/概念之前, 都会先给一大段非形式化的描述, 让人建立起直观的理解, 最后将其形式化地定义下来, 最终就是一个形式化了的系统.
---------------------------------------------------------------------
---------------------------------------------------------------------
再扯两句。我们看到了“形式化[Formal]”这个词。请问，什么是形式化的，什么是非形式化[Informal] 的？一般来说, 建立一个系统的方式, 是先有定义和公理, 然后根据定义和公理, 推导各种引理和定理, 然后 -- 一个系统就建立起来了. 比如欧氏几何, 通过有限的公理和公设, 去证明《几何原本》中的所有"真命题". 这估计是人类史上最早的形式化地建立系统的例子, 这个系统的基础是有限的公理和公设, 然后整个系统就是 -- 欧几里得几何, 也即几何原本. 那么欧氏几何就是形式化的.
由于近代符号逻辑的发展, 形式化(formal methods)一般被纳入符号逻辑/命题逻辑/数理逻辑的数学分支中去了. 不过要注意, 形式化只是一种思考方式, 也就是说形式化方法的本质就像前述说欧氏几何的建立一样. 只不过, 由于数学家们认为, 将这种思考方式符号化从某种程度上有助于思考本身(布尔代数奠基人, 其有一本书的名字就是《The Laws of Thought》). 于是, 在数学上看来, 形式化地建立一个系统需要:
Formal systems in mathematics consist of the following elements:
A finite set of symbols (i.e. the alphabet), that can be used for constructing formulas (i.e. finite strings of symbols).
A grammar, which tells how well-formed formulas (abbreviated wff) are constructed out of the symbols in the alphabet. It is usually required that there be a decision procedure for deciding whether a formula is well formed or not.
A set of axioms or axiom schemata: each axiom must be a wff.
A set of inference rules.
即:
1. 一组有限的符号**, **中的符号用来构建公式. [比如, 令命题p表示"3 + 2 = 5", p就是一个符号, 代表一个命题. 比如, 对两个命题的合取一般表示为 p ^ q, 即, p成立而且q也成立, 就像 C语言中, &&对两个表达式取逻辑乘一样. 对两个命题的析取一般表示为p v q, 即p成立, 或者q成立, 或者二者皆成立]
2. 语法规则, 就是根据符号**(亦称字母表)构建合式公式(原文中的well-formed formulas, 一般数理逻辑中译为合式公式)的规则. [合式公式是由命题常项、命题变项、联结词、括号等组成的符号串, 但不是由这些符号任意组成的符号串都是合式公式]. 语法规则用于判断一个公式是不是合式公式.
3. 一组公理或者公设. 公理和公设必须是合式公式.
4. 一组推理规则.[_三-段-论_神马的]. 即, 形式化方法的本质仍然是: 根据基本的公理和公设, 加上一组推理规则, 然后... 建立整个系统. 就是这个意思. 形式化的方式和别的方式的本质区别在于, 是不是具有有限的基本模型抽象, 然后根据这些基本模型抽象推导出/建立整个系统模型. 对于形式化的方式来说, 由于这种形式化的方式保证了逻辑上的严格性, 在系统日益复杂的情况下, 有可能思考需要回到某个定义本身开始. 因此这种方式被广泛地应用.
***************************************
那么非形式化的方式是什么？就是直观地描述. 如果一上来就给人一套数学形式化描述的东西, 然后让人根据这个东西去推导什么的, 谁都会发疯的. 于是一般在介绍一个形式化的定义/概念之前, 都会先给一大段非形式化的描述, 让人建立起直观的理解, 最后将其形式化地定义下来, 最终就是一个形式化了的系统.
---------------------------------------------------------------------
不感兴趣
开通SVIP免广告
