本节书摘来自华章计算机《从问题到程序：用Python学编程和计算》一书中的第3章，第3.2节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.2 递归
有一种函数定义比较特殊，就是在定义的函数体里调用被定义的函数自身。Python允许这种形式的函数定义，称为递归定义，这样定义出的函数也经常被称为递归函数。但是，这样做带来了一个数学里经常提到的问题：基于自己定义自己，这种形式的定义有意义吗？会不会做出了一个所谓的“循环定义”，完全没有意义？本节讨论这方面的一些情况，并说明递归定义是一种很有用的编程技术。
3.2.1 递归定义的函数
3.2.2 乘幂的计算
3.2.3 循环和递归
前面讨论过循环程序与简单程序（直线型程序和分支程序）之间的不同。上面又提出了递归定义的函数，在其写法中并没有出现循环结构，但同样可能导致重复的计算。这里的情况是通过递归调用，多次重复执行同一个函数的体代码。由此我们可以想一个问题：递归和循环能做的事情类似，那么，两者可以相互替代吗？
人们对这方面的问题做过一些理论研究。一个结果是：如果一个语言中包含了基本语句、顺序组合和条件语句，而且允许以递归的方式定义函数，这样构成的语言就足够强大了，足以描述所有可能的计算过程。另一方面，一个包含了基本语句、顺序组合和循环结构的语言也足够强大，也可以写出所有可能的计算。
进一步说，不难设计出一种方法，采用这种方法，可以根据任何一个循环定义出一个递归函数，在程序里原来写循环的地方调用这个函数，就能得到同样的计算效果。而反过来的情况比较复杂，要把一个递归定义的函数改为不用递归方式定义的函数（称为原函数的非递归实现），有时会遇到一些困难，但也是可以完成的。
上面的理论结果说明递归和循环中有一个就足够了。但为了方便实际的程序开发，各种实际编程语言都引进了一些冗余的机制，包括冗余的控制机制（以及后面将会讨论的数据机制）。例如，Python语言有循环结构，同时也允许递归的函数定义。
作为例子，现在考虑前一小节的乘幂函数，看看怎样做出与之对应的循环实现。
可以看到，在前面power函数的递归实现里，递归调用之间传递两个参数x和n，还有一个是函数的返回值。虽然传递的参数名字不变，但参数的值一直在变化。其中变量n的值不断减小（或者整除2或者减一），x不断求平方。每次遇到指数为奇数时，就是当时x的值作为乘数。按说需要用一个变量记录这个变化的x。但由于Python中函数的参数就是变量，可以直接用参数x记录这个变化的值。另外，为了反映积累的乘积（递归函数的返回值），引进另一个变量p。由于这里用乘法累积信息，p的初值设为1。
根据这些考虑，写出的函数定义如下：
def power(x, n):
p = 1
while n > 0:
if n % 2 != 0:
p *= x
n -= 1
else:
x *= x
n //= 2
return pp是这里的累积变量，循环中把x的一些幂次累积到p上，最终得到x的n次幂。循环里区分了几种情况：指数n等于0时累积工作完成，循环结束，变量p的值即为所需。循环体就是一个if语句，两个分支分别处理指数为偶数和奇数的情况，其中用了几个扩展的赋值语句更新变量。注意，对p的初始化保证，即使这个循环的体一次也没有执行，得到的结果也是对的。
3.2.4 斐波那契数列的计算
3.2.5 最大公约数
最大公约数（Greatest Common Divisor，简写为GCD或gcd）是一个重要的数学概念。整数n的约数就是能整除n的整数，k整除n即为n除以k的余数为0。显然，对任意的n，1和n本身都是其约数。两个整数m和n的最大公约数，就是能同时整除两者的整数中绝对值最大的那个数。由于1是任何整数的约数，两个整数的最大公约数一定存在。本节考虑最大公约数的计算问题，定义完成它的Python函数。这个问题也存在许多求解方法。
朴素解法
最直接的方法是系统化地检查一些整数，直至找到能同时整除两个数的最大数。设函数的参数分别是m和n，为做顺序检查，需要用一个辅助变量k，用它的值做检查。下面的问题是k如何取值。根据前面的经验，最简单的系统化检查方法就是顺序检查，从某个值开始逐一试验，直至到达我们的目标。为此需要设计一个循环，实现这种重复检查。这样，k的取值问题就变成如何取初值，如何更新，如何判断结束。
方法1：令k从1开始递增取值，结束条件是k大于m或n中的某一个。这样就能保证得到结果，因为最大公约数绝不会大于两个数中的任何一个。
下一个问题是如何得到所需结果。m和n可能有许多公约数，变量k最后的值也不会是m和n的公约数，因为它已大于两个数之一。这些情况说明，需要在循环中记录遇到的公约数，为此需要引进新变量。对这个具体问题，只需要引进一个变量，记录已经找到的最大的公约数。例如用变量d，其初值可以设为1，因为1是任何整数的约数。遇到m和n的新公约数时把它记入d，这个语句应该是：
if m % k == 0 and n % k == 0:
d = k; # k是新的公约数，而且更大可以看到，引入d及其初值后，k的取值可以从2开始。函数定义已经很清楚：
def gcd (m, n):
d = 1
k = 2
while k <= m and k <= n:
if m % k == 0 and n % k == 0:
d = k
k += 1
return d这里假定了m和n的值都不小于0。如果m和n没有除去1之外的其他公约数，变量d的初值1就会留下来，也能得到正确结果。
如果考虑任意整数参数，还需要仔细考虑各种情况：
综合起来，在函数的循环之前应该加上几个语句：
if m == 0:
return n
if n == 0:
return m
if m < 0:
m = -m
if n < 0:
n = -n两个参数都是0的情况也自然地处理了，无须专门检查。
在这个示例程序里用了一个辅助变量d，用于记录计算过程中得到的中间结果。根据需要引入辅助变量是程序设计中的一种常用技术。另一个问题也值得注意：许多计算问题都有一些需要处理的特殊情况，应当仔细分析，分别给以处理。其中一件事情就是分析参数的各种可能情况，看看程序是否都能给出正确结果，必要时修改程序，经常需要在主要代码前面加一些条件判断，也可能需要加入另外的处理语句。
方法2：令k从某个大数开始递减取值，这样，找到的第一个公约数就是最大公约数。可以令k的初值为m和n中较小的一个，在没有遇到公约数的情况下递减。结束条件是：或者k值达到1，或者已经找到了公约数。由于1总是两个数的公约数，因此前一条件被后一条件覆盖。有关程序留作读者的练习。
上面这两种求解方法的共同点是采用重复测试的方法，用每一个数去检查条件是否成立。这里采用的是通用的生成与检查方法，很多问题都能这样求解。为应用这种方法，需要设计并生成需要检查的数据集，实现适当检查的方法。这种方法的缺点是效率通常比较低，如果需要检查的数据集合很大，程序中的循环就要反复执行很多次。一般而言，如果能找到解决具体问题的特殊方法，就不应该选用这种“通用”方法。
辗转相除法
对于求最大公约数的问题，古代科学家已经提出了更有效的计算方法，这就是著名的欧几里得算法（欧氏算法），即辗转相除法。下面介绍欧几里得算法的程序实现。首先，不难用递归形式给出辗转相除法求最大公约数的定义：
这里假定m和n都是自然数，而且m不为0。
函数定义1（递归定义）：先假定函数的第一个参数非0，而且两个参数都不小于0。下面的函数定义直接对应于辗转相除法的数学定义：
def gcd(m, n):
if n % m == 0:
return m
return gcd(n % m, m)这个函数很简单，对欧几里得算法的研究保证该函数的计算一定能结束。这个函数的计算速度很快，快于前面的顺序检查，参数较大时优势更明显。
为处理各种特殊情况，可以另外写一个函数，其中调用上面的函数。这也是程序设计中常见的技术。下面是求最大公约数的主函数：
def gcd_main(m, n):
if m < 0:
m = -m
if n < 0:
n = -n
if m == 0:
return n
return gcd(m, n)函数定义2（循环方式）：辗转相除也是一种重复性工作，其中反复求余数。前面用递归的方式定义函数，也可以通过循环实现。在写程序前，先分析一下应当如何写循环：
1）循环开始时，m和n是求最大公约数的出发点。
2）每次循环判断n % m是否为0。如果为0，m就是最大公约数，结束。
3）否则做变量更新：更新后的n取原来m的值，而m取原来n % m的值。这两个变量更新可以用一个平行赋值实现：
m, n = n % m, m下面是这个函数的一种定义，其中假定两个参数的值均不小于0。把这一函数补充完整的工作留给读者考虑。
def gcd(m, n):
if m == 0:
return n
while n % m != 0:
m, n = n % m, m
return mn的值为0以及m和n的值都为0的情况没有特殊处理，因为这些处理都已经包含在定义里了。读者很容易弄清楚这一点。上面函数里也有一个较复杂的循环。按照前面说法，一个循环中总要维持某种不变关系，以保证循环的正确性。那么，上面函数里的这个循环维持的是变量之间的什么关系呢？这一点也请读者考虑。
这个例子也说明了平行赋值的作用。在上面的函数里采用了平行赋值，既简单又清晰，意义也正确。如果将其分开写为两个单独的赋值语句，无论怎样排序都不能得到正确结果。当然，这并不说明用简单赋值不能解决这个问题，但要完成同样功能，需要另外引进一个辅助变量。请读者自己验证这些论断。
3.2.6 不容易用循环求解的递归问题
3.2.7 更复杂的递归情况
前面讨论中出现的递归都是一个函数在体中调用自身，这种递归可以称为自递归。有时也会出现需要两个或多个函数相互调用，形成复杂的递归情况。其中最简单的情况就是两个函数相互递归调用，例如在f里调用g，在g里调用f。
如果需要定义两个相互调用的函数，就会遇到一个问题：无论先定义哪个，其函数体里总需要调用另一个尚未定义的函数。还好，在Python语言里，怎么排列两个函数定义都没问题。在处理函数的定义时，Python解释器并不检查其中调用的函数有无定义，只要在实际调用时被调函数有定义，能找到它，就万事大吉了。如果执行到一个函数调用时被调用函数还没有定义，Python解释器自然要报错。
下面是两个相互递归的函数，它们分别判断参数的奇偶：
def even(n):
if n == 0:
return True
else:
return odd(n-1)
#even(4) # 在这里调用将会报销
def odd(n):
if n == 0:
return False
else:
return even(n-1)如果在函数even的定义之后调用even(4)，系统就会报错。因为当解释器处理到这一点，函数odd还没有定义。在odd有定义后，写even(4)就没问题了。
这个例子本身并没有实际意义，只是用来说明情况。在实际编程中，可以出现更复杂的递归情况，这里就不举例了。
