迹忆客 专注技术分享

在今天的教程中，我们将通过递归及其类型来了解尾递归。 此外，我们还将学习如何在 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

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

它只适用于少量； 所以开发者想出了简单递归的优化方案，那就是Tail Recursion。

递归的类型

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

1. 头部递归
2. 尾递归 头递归是函数在开始时调用自身，而尾递归是函数在递归结束时调用自身。

两者各有利弊，但尾递归通常被认为更有效。 让我们在下面更详细地了解它。

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)

输出:

500500

使用 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)

输出:

1
2
3
4
5
6
7
8
9

尾递归函数的好处

尾递归函数是一种递归函数，其中函数中的最后一条语句是对递归函数的调用。

此函数比非尾递归函数更有效，因为它不需要函数跟踪递归调用的中间值。

它使尾递归函数更高效且更易于理解。 使用尾递归函数有很多好处。

1. 尾递归的主要好处之一是它更容易优化。 因为尾调用是函数中最后发生的事情，编译器可以更容易地优化它。 这意味着尾递归函数在时间和空间方面可以更高效。
2. 尾递归的另一个好处是它通常更容易理解。 因为递归调用是函数中最后发生的事情，所以更容易看出发生了什么。 它可以使尾递归函数更易于调试和维护。
3. 它们比非尾递归函数更有效，因为它们不需要跟踪中间值。
4. 它们更容易推理，因为函数调用堆栈在函数末尾总是空的。 此外，尾递归函数可以更容易地并行化。
5. 我们可以轻松地将它们转换为迭代程序，这在某些情况下效率更高。
6. 它可以使函数运行得更快并使用更少的内存。 此外，它还可以更轻松地编写正确的代码。