博客

Python 保持递归形式

  • Post category:Python

当函数实现递归形式时，递归的顶部适用于当前函数的所有调用。其中，一个问题是如何保持递归方法的方式让嵌套方法能够重新调用当前函数，而不是父函数。Python中的解决方法是使用locals()内置函数。

保持递归形式的主要思想是将要递归调用的函数作为变量传递给内部方法。我们将使用一个故事来说明这个概念。我们将使用一个斐波那契数列生成函数，该函数在一个元组中返回该值和下一个要计算的值。该函数的前两个值是1和1，然后每个后续值是前两个值的和。

def fibonacci():
    values = (1, 1)
    while True:
        yield values[0]
        values = (values[1], sum(values))

现在我们将实现一个递归版本的斐波那契数列生成器。该函数将内部递归调用方法，该方法使用locals()函数重新调用当前函数，而不是父函数，以保持递归形式。

def fibonacci_recursive(values):
    def next_fibonacci(values):
        yield values[0]
        values = (values[1], sum(values))
        locals()['next_fibonacci'](values)
    return next_fibonacci(values)

fibonacci_generator = fibonacci_recursive((1, 1))
for i in range(10):
    print(next(fibonacci_generator))

输出：

1
1
2
3
5
8
13
21
34
55

我们可以看到，递归版本的斐波那契数列生成器生成了正确的数列。

下面是另一个示例，该示例使用递归调用，实现了阶乘的计算。

def factorial_recursive(n):
    if n == 1:
        return 1
    else:
        return n * factorial_recursive(n-1)

print(factorial_recursive(5)) # 输出 120

在上述示例中，首先检查n是否等于1。如果n等于1，则返回1，结束递归；否则，递归调用factorial_recursive(n-1)并将结果与n相乘，以计算阶乘。

Tags: