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，此时可以保证从coprime到1 + 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

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