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

Question

我想我理解了教科书中对尾部递归函数的定义：在函数调用后不执行任何计算的函数。我还发现，作为一个结果，尾部递归函数的内存效率会更高，因为它每次调用只需要一条记录，而不是每次都需要保留一条记录（就像在普通递归中那样）。

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

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

我最初给出的答案是，根据定义，它不是尾部递归的（因为外部调用是在计算内部调用之后执行的，所以其他计算是在第一次调用之后完成的），所以通常具有嵌套递归调用的函数不是尾部递归的；另一方面，在实践中也是一样的，因为它共享尾部递归函数的副作用：在我看来，整个函数需要一个激活记录。这是真的吗？

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

Answer 1

你的理解只是部分正确。

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

现在回到你的实际问题，内部调用不是尾递归的，因为它必须回到你的调用并做其他事情。但是外部调用是尾递归的。