python - 在尾递归中重用先前分配的空间

Question

我正在从尾递归中读取尾递归 - LeetCode

它指出python不支持尾递归优化

尾递归函数可以作为非尾递归函数执行，即使用成堆的调用堆栈，而不影响结果。通常，编译器会识别尾递归模式，并优化其执行。然而，并不是所有的编程语言都支持这种优化。例如，C、C++ 支持尾递归函数的优化。另一方面，Java 和 Python 不支持尾递归优化。

我不明白这是什么tail recursion optimization意思。

本教程提供了一个示例

def sum_non_tail_recursion(ls):
    """
    :type ls: List[int]
    :rtype: int, the sum of the input list.
    """
    if len(ls) == 0:
        return 0

    # not a tail recursion because it does some computation after the recursive call returned.
    return ls[0] + sum_non_tail_recursion(ls[1:])

def sum_tail_recursion(ls):
    """
    :type ls: List[int]
    :rtype: int, the sum of the input list.
    """
    def helper(ls, acc):
        if len(ls) == 0:
            return acc
        # this is a tail recursion because the final instruction is a recursive call.
        return helper(ls[1:], ls[0] + acc)

    return helper(ls, 0)

并说明

请注意，在尾递归中，我们知道一旦从递归调用返回，我们也将立即返回，因此我们可以跳过返回的整个递归调用链并直接返回到原始调用者。这意味着我们根本不需要所有递归调用的调用堆栈，这节省了我们的空间。

例如，在步骤 (1) 中，将分配堆栈中的空间f(x1)以便调用f(x2). 然后在步骤 (2) 中，该函数f(x2)将递归调用f(x3). 然而，系统可以简单地将先前分配的空间重新用于第二次递归调用，而不是在堆栈上分配新空间。最后，在 functionf(x3)中，我们达到了基本情况，该函数可以简单地将结果返回给原始调用者，而无需返回之前的函数调用。

这里的关键思想是我们可以跳过整个递归调用链并重用之前分配的空间。

至于python不支持尾递归优化。

这是否意味着python仍然需要一个调用堆栈并且不会在尾递归中重用先前分配的空间？

标签： pythonrecursion