recursion - 什么是函数的尾部上下文？

Question

在讲座期间，我得到了尾部调用的定义:尾部调用是发生在尾部上下文中的调用表达式。我在 The Revised Report on the Algorithmic Language Scheme 中查找了尾部上下文的定义:

A tail call is a procedure call that occurs in a tail context. Tail contexts are defined inductively. Note that a tail context is always determined with respect to a particular lambda expression.

我认为这些都没有真正阐明尾部上下文是什么，有人可以给出一个对初学者来说可能更容易理解的解释吗？

Answer 1

尾部是 animal 函数的最末端。直观上，如果函数除了将求值结果返回给其调用者之外什么都不做，则求值发生在尾部上下文中。

关于尾部上下文的关键观察是，调用框架中不需要任何内容​​(除了对调用者的引用)，允许尾部上下文中执行的调用重用调用框架。这样做可以将某些递归算法的空间要求从 O(N) 更改为 O(1)，或者在快速排序等不完美分区的算法的情况下更改为 O(log N)。

程序流分析可以识别回收调用帧的其他可能机会，但在许多语言中，尾部上下文可以通过简单的语法分析来识别。对于Scheme，程序在语言文档中指定，并在原始帖子中链接。如果可以通过这种方式识别尾部调用，Scheme 要求对其进行优化。

在许多其他语言中，尾部调用优化不是必需的，在某些情况下甚至是不可能的。例如，在 C++ 中，可能存在隐式析构函数，需要在最后一次调用之后和返回之前运行；此外，返回的值可能需要转换为不同的类型。在调用框架可用于自省(introspection)的语言中(例如 JavaScript)，调用框架回收将修改可观察的程序行为。