递归调用：程序整体性的优化锦囊

递归是强大的问题解决工具，是程序设计中的一种重要思想和机制，递归有助于写出清晰易懂的代码，能有效提高程序的整体风格

什么是递归

在数学及程序设计方法学中为递归下的定义是这样的：若一个对象部分地包含它自己，或用它自己来定义自己，则称这个对象是递归的；若一个过程直接或间接地调用自己，则称这个过程为递归的过程。

简而言之，递归方法就是直接或间接地调用其自身，递归方法可以用来将一些复杂的问题简化，C++也像其他语言一样支持递归。

在日常生活中，递归的例子是十分普遍的

下面简单举几个例子来阐释递归的概念

---- 字 典 ----

字典是递归定义的典型实例。字典中任何一个词都是由“其他词”来解释或定义的，但是“其他词”在被定义或解释的时候又会间接或直接地用到那些由它们定义的词。使用者可以读懂字典中全部词汇的释义，前提是使用者必须掌握少量非常基础的词的含义。当使用者查询某个生僻的词汇时，他发现释义中的某个词汇无法理解，因此他继续在字典中查询那些暂时不能理解的词汇释义。如此继续下去，但此过程最后必然终止，因为最后所有的释义都归结为读者已经了解的常见意思，否则字典使用者将陷入一个无解的问题陷阱中。

---- 无 穷 故 事 ----

大家一定听过那个关于老和尚讲故事的“无穷故事”：

从前有座山，山里有个庙，庙里有个老和尚，老和尚正在给小和尚讲故事，故事说“从前有座山，山里有个庙，庙里有个老和尚，老和尚正在给小和尚讲故事，故事说……”。

当然这是一个不好的例子，因为它将意味着死循环。递归的能力在于用有限的元素来定义对象的无限集合，所以生活中的递归往往存在这种永无终止的情况。但就程序设计而言，递归是需要有边界条件的。在程序设计语言中应当避免这种无穷调用。

---- 科 赫 曲 线 ----

1904 年，瑞典数学家海里格·冯·科赫（Helge von Koch）提出了后来以他名字命名的分形曲线——科赫曲线，这也是最早被描述出来的分形曲线之一。

设想一个边长为1 的等边三角形，取每边中间的三分之一，接上去一个形状完全相似的但边长为其三分之一的等边三角形，结果是一个六角形。再取六角形的每个边做同样的变换，即在中间三分之一接上更小的等边三角形，以此重复，直至无穷。

显然

每次变化后图形的面积和周长都会增加，但是总面积的极限却趋向一个有限值（图形的面积永远不会超过初始三角形的外接圆），而图形的周长却具有无限长度。相比于平常的几何图形，科赫曲线的这种特殊性质显得非常不可思议。此外，科赫曲线还具有极其复杂而精细的自相似结构，即某一个细节放大后将呈现出与整体的惊人相似。科赫曲线的生成方式就是一种递归。

通常在下面3 种情况下递归的方法会被用到。

• 定义是递归的
• 数据结构是递归的
• 问题的解法是递归的

①来看关于定义是递归的这方面的例子

在数学上常用的阶乘函数、斐波那契序列等，它们的定义和计算都是递归的。例如，阶乘函数的定义为：

这个定义十分容易理解而且易于使用，下面来看看3!是如何根据这个定义求得的：

3! = 3 × 2! = 3 × (2 × 1!) = 3 × [2 × (1 × 0!)] = 3 × [2 × (1 × 1)] = 6

下面给出了阶乘的递归求解函数。

②某些数据结构是递归的。

例如，链表就是一种递归的数据结构。从概念上讲，单链表可以递归地定义为一个节点，当该节点的指针域为NULL 时，就表明此链表是一个单链表，这个节点的指针域也可以指向另一个单链表，而这个单链表具有同样的结构。

此外，作为另外一种常用的数据结构，树也可以采用递归的方式来描述。首先，一棵树要么是空的，要么由根和若干非空子树组成（子树的数目可以为零），且这些子树的根都通过一条边连到根上。每个子树同样具有这样的结构，要么为空，要么由根和若干非空子树组成。特别需要说明的是对于递归的数据结构，采用递归的方法来编写算法是比较简便的。下面举一个编译原理中的例子。

编译程序需要能够对语言句型进行分析。所谓句型分析就是构造某种算法来判断所给的符号串是否为某一文法的句型或句子。对于一个编译程序而言，无论是在词法分析阶段，还是在语法分析阶段，都需要用到句型分析，可见句型分析的重要性。在进行句型分析时，需要通过递归技术构造树结构来解决问题。

所有的程序设计语言都可以写出像1 ∗ (2 + 3)这样的算术表达式。下面就以此为例来看看如何描述和判断算术表达式。一个算术表达式可以是如下的任何一种形式。

A．一个数值常量。

B．一个表示数值常量或变量的标识符。

C．一个包含在括号中的算术表达式。

D．被一个二元运算符分开的两个算术表达式。

像这样的定义在描述程序设计语言的语法时应用十分广泛。任何编译程序的第一步都是使用这些定义来拆解原始编程语言的语句。这个过程的结果被称为分析树。反复应用定义来将一个给定值分解成若干部分，然后再检查每一部分的合法性。基本条件将指导判断某些特定值是否合法。

对于上面的例子首先应用规则D。

这样可以把原始输入拆解成3 个部分。即1、∗、(2 + 3)，并对它们进行分析。结果显示如果以下内容被确定，那么就可以判定原始的输入是否

为一个合法的算术表达式了。

(a) 1是一个算术表达式。

(b) ∗是一个二元运算符。

(c) (2 + 3)是一个算术表达式。

通过规则A可以判定(a)是正确的，在已知的二元运算符表中查询∗便可判定它是一个二元运算符，(b)是正确的。综上可知为了判定原始输入是一个合法的表达式，仅需判定(c)的合法性即可。而判定(c)需要如下几步。

应用规则C可知，只要判定2 + 3是一个算术表达式就可以判定(2 + 3)是一个算术表达式。为了判定2 + 3是一个算术表达式这里应用规则D将2 + 3分成3 个部分，即2、+和3。应用上面的规则可知。

(d) 2是一个算术表达式。

(e) +是一个二元运算符。

(f ) 3是一个算术表达式。

通过规则A可以很容易判定(d)和(f)的合法性。而在已知的二元运算符表中查询+则可判定它是一个二元运算符。因此所有的条件都表示原始输入是一个合法的算术表达式。

整个判定过程不仅认定了原始输入的合法性，而且给出了表达式的结构，下图为原表达式的分析树。