Python中的尾部递归

Python 4月前 9

在今天的教程中，我们将通过递归和其类型来学习尾部递归的知识。此外，我们还将学习如何在Python中调用尾部递归，并探索使用它的一些好处。

Python中的递归

在计算机科学中，递归是一种解决问题的方法，其中一个函数在体内调用自己，直到满足一个特定的条件。

它是有价值的方法之一，它有很多现实生活中的用例；然而，它有一些限制，那就是它的空间和时间的复杂性。让我们看看下面这个递归的例子。

示例代码：

def factorial(n):
    if (n==1 or n==0):
        return 1
    else:
        return (n * factorial(n - 1))  # recursive call
num = 4;
# In this case factorial is 4x3x2x1 = 24
print(f"The factorial of {num} is {factorial(num)}")

输出：

The factorial of 4 is 24

递归使用堆栈来保存局部变量，每一次递归的运行都会增加其大小，而堆栈的大小是有限的。这也是开发者开始考虑一些优化解决方案的原因。

它只适合于小数字；这就是为什么开发人员想出了简单递归的优化解决方案，这就是尾部递归。

递归的类型

谈到递归函数，主要有两种类型：

头部递归
尾部递归

头部递归是指函数在开始时调用自己，而尾部递归是指函数在递归结束时调用自己。

两者都有好处和缺点，但一般认为尾部递归的效率更高。下面让我们更详细地了解它。

Python中的尾部递归

Python中的尾部递归是对简单递归的优化解决方案；它允许无限的递归而不引起任何堆栈溢出错误。

但是在进入尾调用递归的细节之前，让我们了解一下尾调用递归的定义；call ，意味着我们正在考虑调用该函数，而tail ，意味着最后一个。所以，调用尾部递归方法意味着该函数从函数的末端重复调用自己。

现在，大多数编程语言都是尾部递归的，这意味着他们正在对递归函数进行优化。

在Python中调用尾部递归函数

在Python中，有两种方法可以调用尾部递归函数。第一种是使用return 关键字，第二种是使用yield 关键字。

使用`return` 关键字来调用一个尾部递归函数

首先，你可以使用return 关键字来从一个函数中返回一个值。然而，你必须小心使用这个关键字，因为它将立即终止函数。

这意味着你只能在确定该函数不需要再被调用的情况下使用它。记住，当我们使用’return’关键字时，函数会返回最后的计算值。

这是最常见的调用尾部递归函数的方式。例如，请看下面的代码栅栏。

示例代码：

def trisum(n, csum):
    while True: # Change recursion to a while loop
        if n == 0:
            return csum
        n, csum = n - 1, csum + n # Update parameters instead of tail recursion
trisum(1000,0)

输出：

使用 `yield` 关键字来调用一个尾部递归函数

另一种调用尾部递归函数的方法是使用yield 关键字。这个关键字允许你从一个函数中返回一个值而不终止该函数。

你可以重复调用该函数，每次返回一个不同的值。这对于需要返回大量数值的函数是很方便的。

当使用yield 关键字时，函数将yield 最后的计算值。这是一种不太常见的调用尾部递归函数的方式，但在某些情况下会有帮助。

示例代码：

def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a
b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)