Python 递归代替循环

Python 递归代替循环语句,函数式编程不依赖循环语句,也不产生跟踪循环状态的开销,而使用相对简单的递归语句。在一些语言中,代码中的递归会在编译阶段被编译器通过尾调用优化(tail call optimization,TCO)技术转换成循环语句。本节简单介绍一些递归用法。

接下来介绍如何通过遍历测试一个数是否为质数。质数是只能被1和本身整除的自然数。我们可以定义一个简单的低性能算法,检查2到这个数之间的所有自然数能否整除它。该算法的优点是简单,可以作为欧拉计划中问题的解法。如果你对求解该问题的高性能算法感兴趣,可以参考米勒-拉宾素性检验算法。

我们使用“互质”表示两个数除了1之外没有其他公约数,比如2和3是互质的,而6和9不是互质的,因为它们除了1之外,还有公约数3。

这样就可以把测试一个数是否为质数,转换为下面这个问题:自然数 n 是否与自然数 p 的任意取值互质,其中 p^2<n,或者简化成:n 是否与所有满足条件 2\leq p^2<n 的数 p 互质?

不妨把上面的陈述转换为如下数学公式。

Python 递归代替循环语句

对应的Python表达式如下。

not any(n % p == 0 for p in range(2,int(math.sqrt(n)) + 1))

从数学公式转换而来的更准确的写法是all(n % p != 0 ... ),但它需要对所有 p 的可能取值严格求值,而上面的not any版本会在碰到第一个True值的时候结束计算。

这个简单的表达式中包含一个for循环,所以不是纯粹的、无状态的函数式编程风格。我们可以把它转换成处理一个集合的函数:自然数 n 是否与 [2, 1+ \sqrt{n}] 内的所有数互质?其中符号[)代表半开区间:下限在范围内,上限不在范围内,与Python函数range()的取值方式一致。由于我们只在自然数范围内讨论问题,所以平方根的值会自动转换为整数。
因此可以如下定义测试质数的公式。

Python 递归代替循环语句

基于一组数值定义函数时,集合为空是基础形式,递归将非空集合处理为:对集合中一个数的处理结果加上对剩余数值集合的处理结果,类似于下面的公式。

Python 递归代替循环语句

该公式通过判断以下两种情况给出测试结果。

  • 当范围为空时,a=b,对类似于coprime(131071, [363, 363))的表达式求值。由于范围内不含可用取值,所以返回True

  • 当范围非空时,对类似于 coprime(131071,[2,363)) 的表达式求值。在这种情况下,表达式会分解为(131071 mod 2)\not=0 ^ coprime(131071,[3,363)),其中第一部分的返回值为True,所以需要递归对第二部分求值。

作为练习,读者可以尝试将上面的递归算法由向上缩减范围改为向下缩减范围,即在递归形式中用[a, b-1)代替[a+1, b)

也许有人认为空区间应该是a≥b而非a = b,其实是不必要的。由于a每次增加1,可以保证a≤b始终成立,并不会因某种差错导致a越过b。所以无须为空区间设置过多限制条件。

实现前面定义的质数的Python代码如下。

def isprimer(n: int) -> bool:
    def isprime(k: int, coprime: int) -> bool:
        """Is k relatively prime to the value coprime?"""
        if k < coprime*coprime: return True
        if k % coprime == 0: return False
        return isprime(k, coprime+2)
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    return isprime(n, 3)

上面的代码使用了递归定义的函数isprimer(),接收类型为整数的参数n,返回布尔值。
半开区间 (2,1+\sqrt{n}) 的下限参数a改名为coprime以更好地表达其作用:通过改变它来缩小测试范围。这里的基础形式是n < coprime * coprime,此时可以保证从coprime1 + math.sqrt(n)为空。

其中将非严格的and操作替换成一条单独的if测试语句:if n % coprime == 0。最后的return语句使用新的coprime参数对函数进行递归调用。

由于递归发生在函数尾部,所以这是一个尾递归的例子。

函数中增加了对待测试自然数的限制条件:大于2的奇数。由于2是唯一的偶质数,所以大于2的偶数显然不是质数,无须测试。

这个示例的重点是递归函数中的两种情况都很简单,用待测试值作为内部isprime()函数的参数,可以让我们在递归调用函数时,通过改变参数值来确保取值范围不断缩小。

虽然这样的算法通常简洁明了,但在Python中使用这样的算法要注意下面两个问题。

  • Python对嵌套递归的深度有限制,不能随意定义基础形式。
  • Python的编译器没有尾递归功能。

递归深度上限默认为1000,对于多数算法来说足够了。也可通过sys.setrecursionlimit()函数修改这个值,但不建议把它改得过大,否则算法使用的内存会超过操作系统的物理内存,进而导致Python解释器崩溃。

当用isprime()函数测试大于1 000 000的数时就会超过递归上限。即使我们优化算法,用它只测试质数,而非所有自然数,这个算法仍然只能测试第1000个质数(即7919)的平方(即62 710 561)以下的自然数。

有些函数式语言可以优化类似于isprime()这样的函数,把isprimer(n, coprime+1)这样的递归调用转换为低开销循环语句。但这种优化往往会弄乱调用栈,难以调试优化过的程序。Python不进行此类优化,而为了保证清晰与简洁,牺牲了性能和内存使用,这也意味着我们必须手动进行优化。

在Python中,如果用生成器表达式代替递归函数,实际效果相当于手动进行了尾调用优化,从而不必依赖其他函数式语言中编译器的优化能力。
使用生成器表达式完成尾调用优化的代码示例如下。

def isprimei(n: int) -> bool:
    """Is n prime?

    >>> isprimei(2)
    True
    >>> tuple( isprimei(x) for x in range(3,11) )
    (True, False, True, False, True, False, False, False)
    """
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, 1+int(math.sqrt(n)), 2):
        if n % i == 0:
            return False
    return True

该函数满足函数式编程的许多要求,但用生成器表达式取代了单纯的递归调用。

在生成器表达式中常用for循环优化递归函数。

对于大的质数,上面的算法速度不算快,但对于合数,往往能很快给出结果。以 M_{61} = 2^{61}-1为例,上述算法需要花费数分钟才能确定它是质数,毕竟整个过程测试了1 518 500 249个可能的因子。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程