第3章 递归——自己调用自己
递归（Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中又调用函数自身的方法。递归是一种奇妙的思考问题的方法，通过递归的这种思路，可简化问题的定义。
3.1 从前有座山，山里有座庙
递归一词常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。
3.1.1 老和尚讲的故事
将时光往前推，在中国还流传着这样一个有趣的故事：
从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”
怎么样？这个故事就是不断重复着老和尚讲的故事，有趣？还是无聊？
不管怎样，这个故事可以不断地重复，一直讲下去。
这就是生活中一个用递归形成的故事。
3.1.2 德罗斯特效应
再来看一张图，如图3-1所示为一张网页的截图，在网页图中又包括相同的一份较小的截图，在小图中又包含一份更小的截图，……，这样就形成了一幅递归形式的图形。
图3-1
图3-1所示的图形称为德罗斯特效应（Droste effect），是递归的一种视觉形式，是指一张图片的某个部分与整张图片相同，如此产生无限循环。这种照片是通过名为Mathmap的数学软件制作出来，使用PhotoShop的Droste Effect滤镜也可制作出这种效果。
3.1.3 什么是递归
那么，什么是递归呢？
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
例如，我们人类的发展繁衍中，人之间的辈份就是一种递归（如图3-2所示），在这个递归中首先定义一个基本情况，接着递归定义，具体情况如下：
图3-2
A的父母是A的祖先（这是基本情况）。
A祖先的双亲同样是A的祖先（递归步骤）。
对于递归，一种便于理解的心理模型，认为递归对对象的定义是按照“先前定义的”同类对象来定义的。
例如：要求能移动100个箱子，该怎么移动？
首先移动1个箱子，并记下它移动到的位置，然后再去解决较小的问题（由于已移动了1个箱子，剩下99个箱子），这时的问题就简化为“怎样才能移动99个箱子？”，……不断重复，到最后，问题将简化为“怎样移动1个箱子”，如图3-3所示。
图3-3
类似的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数，如图3-4所示。
图3-4
3.1.4 用递归能解决哪些问题
递归是一种非常接近自然思维的思想，其实了解多了以后，用起递归来是非常自然的，但不是每个场合使用递归都是合适的。通常递归方法适合于层次结构本身就是递归定义的情况，比如二叉树的遍历，因为二叉树的定义就是“一颗空树，或者一个节点＋左右两颗子二叉树”，它的定义就是递归的，所以用递归操作相当方便。
简单来说，递归问题，可以划分为一个或多个子问题，而处理子问题的规则与处理原问题的规则是一样的。
如图3-2所示的祖先问题、用集合论对自然数的定义问题，以及老和尚讲的故事，都是无穷无尽的。通常意义上来说，对于一个无穷尽的问题，是没办法编写程序来解决的，因为程序没有办法结束。
虽然常见的递归问题都没有尽头，不过，我们可以找到起点，这时可从某一个指定的终点开始，向起点方向运行，当到达起点位置时，即可结束递归调用。
那么，在实际应用中要使用递归算法，通常需要分析以下3方面的问题：
每一次递归调用，在处理问题的规模上都应有所缩小（通常问题规模可减半）。
相邻两次递归调用之间有紧密的联系，前一次要为后一次递归调用做准备，通常是前一次递归调用的输出作为后一次递归调用的输入。
在问题的规模极小时，必须直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的（以规模未达到直接解答的大小为条件），无条件递归调用将会成为死循环而不能正常结束。
根据上面的描述，在设计递归算法时，主要需考虑以下两方面的问题：
确定递归公式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。
确定边界（终了）条件。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。
3.1.5 一个简单例子：求最大公约数
求最大公约数是数学中一个简单的问题。
如果有一个自然数A能被自然数B整除，则称A为B的倍数，B为A的约数。几个自然数公有的约数，叫做这几个自然数的公约数。这些公约数中最大的一个公约数，称为这几个自然数的最大公约数，简称为GCD。
例如，在2、4、6这3个数中，2就是2、4、6的最大公约数。
怎么求最大公约数呢？早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。
辗转相除法的方法是用较大的数M除以较小的数N，较小的除数N和得出的余数R构成新的一对数，继续重复前面的除法（用较大数除以较小数），直到出现能够整除的两个数，其中较小的数（即除数）就是最大公约数。
例如，求153和123的最大公约数，操作过程如下：
所以，153和123的最大公约数就是3。
可以看出，在用辗转相除法求最大公约数时，每次相除后的除数N和余数R都将原来的问题规模缩小，而且有一个边界条件（两数能够整除，即余数为0）。有这两条，就可使用递归算法来解这个问题，处理流程如图3-5所示。
图3-5
根据图3-5所示的流程，可编写出以下C语言程序。
在以上程序中，定义了一个gcd()函数，在这个函数中调用gcd()函数，这样就形成了递归调用。在这个函数内部通过辗转相除，然后判断余数是否为0，若为0就返回n值，否则递归调用gcd()函数进行辗转相除。
怎么样，递归调用函数是不是很简单呢？