《从问题到程序:用Python学编程和计算》——3.2 递归-阿里云开发者社区

开发者社区> 华章出版社> 正文
登录阅读全文

《从问题到程序:用Python学编程和计算》——3.2 递归

简介:

本节书摘来自华章计算机《从问题到程序:用Python学编程和计算》一书中的第3章,第3.2节,作者 裘宗燕,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.2 递归

有一种函数定义比较特殊,就是在定义的函数体里调用被定义的函数自身。Python允许这种形式的函数定义,称为递归定义,这样定义出的函数也经常被称为递归函数。但是,这样做带来了一个数学里经常提到的问题:基于自己定义自己,这种形式的定义有意义吗?会不会做出了一个所谓的“循环定义”,完全没有意义?本节讨论这方面的一些情况,并说明递归定义是一种很有用的编程技术。

3.2.1 递归定义的函数

image
image

3.2.2 乘幂的计算

image
image
image
image

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 p

p是这里的累积变量,循环中把x的一些幂次累积到p上,最终得到x的n次幂。循环里区分了几种情况:指数n等于0时累积工作完成,循环结束,变量p的值即为所需。循环体就是一个if语句,两个分支分别处理指数为偶数和奇数的情况,其中用了几个扩展的赋值语句更新变量。注意,对p的初始化保证,即使这个循环的体一次也没有执行,得到的结果也是对的。

3.2.4 斐波那契数列的计算

image
image
image
image
image
image
image
image
image
image
image

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就会留下来,也能得到正确结果。

如果考虑任意整数参数,还需要仔细考虑各种情况:

image

综合起来,在函数的循环之前应该加上几个语句:

    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总是两个数的公约数,因此前一条件被后一条件覆盖。有关程序留作读者的练习。

上面这两种求解方法的共同点是采用重复测试的方法,用每一个数去检查条件是否成立。这里采用的是通用的生成与检查方法,很多问题都能这样求解。为应用这种方法,需要设计并生成需要检查的数据集,实现适当检查的方法。这种方法的缺点是效率通常比较低,如果需要检查的数据集合很大,程序中的循环就要反复执行很多次。一般而言,如果能找到解决具体问题的特殊方法,就不应该选用这种“通用”方法。

辗转相除法

对于求最大公约数的问题,古代科学家已经提出了更有效的计算方法,这就是著名的欧几里得算法(欧氏算法),即辗转相除法。下面介绍欧几里得算法的程序实现。首先,不难用递归形式给出辗转相除法求最大公约数的定义:

image

这里假定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 m

n的值为0以及m和n的值都为0的情况没有特殊处理,因为这些处理都已经包含在定义里了。读者很容易弄清楚这一点。上面函数里也有一个较复杂的循环。按照前面说法,一个循环中总要维持某种不变关系,以保证循环的正确性。那么,上面函数里的这个循环维持的是变量之间的什么关系呢?这一点也请读者考虑。

这个例子也说明了平行赋值的作用。在上面的函数里采用了平行赋值,既简单又清晰,意义也正确。如果将其分开写为两个单独的赋值语句,无论怎样排序都不能得到正确结果。当然,这并不说明用简单赋值不能解决这个问题,但要完成同样功能,需要另外引进一个辅助变量。请读者自己验证这些论断。

3.2.6 不容易用循环求解的递归问题

image
image
image
image
image
image
image
image

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)就没问题了。

这个例子本身并没有实际意义,只是用来说明情况。在实际编程中,可以出现更复杂的递归情况,这里就不举例了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: