algorithm - 嵌套递归调用 - 这是尾递归吗？

Question

我认为我理解尾递归函数的教科书定义：函数调用后不执行任何计算的函数。因此，我也知道尾递归函数的内存效率会更高，因为每次调用它只需要一条记录，而不是每次都需要保留一条记录（就像在正常递归中一样）。

对我来说不太清楚的是这个定义如何应用于嵌套调用。我将提供一个示例：

func foo91(x int)
    if(x > 100):
        return x - 10
    else:
        return foo91(foo91(x+11))

我最初想出的答案是它不是尾递归定义的（因为外部调用是在评估内部调用之后执行的，所以其他计算在第一次调用之后进行），所以一般嵌套递归调用的函数不是尾递归的；另一方面，它在实践中是相同的，因为它共享尾递归函数的副作用：在我看来，整个函数需要单个激活记录。真的吗？

嵌套递归函数调用通常是相当大的尾递归吗？

标签： algorithmrecursiontail-recursion

Answer 1

你的理解只是部分正确。

您正确定义了尾递归。但它是否真的有效取决于实现。在像 Scheme 这样的一些语言中是这样。但大多数语言都像 JavaScript，但事实并非如此。特别是关键的权衡之一是使尾递归有效意味着您丢失了堆栈回溯。

现在对于您的实际问题，内部调用不是尾递归，因为它必须回到您的调用并执行其他操作。但是外部调用是尾递归的。