是否有一种递归函数/算法，其中使用堆栈帧是不可避免的(不能完全尾递归)

Question

我试图提出递归算法/函数的例子，这些算法/函数不能以避免使用大量堆栈内存的方式重写（即不能完全尾递归或使用不使用堆栈的循环重写）。 这样的功能存在吗？

我认为快速排序可能是一个候选者，但不确定是否可以重写它以使用单个尾递归函数调用。

Answer 1

在一般情况下，每个需要多次调用的算法都无法在没有回溯堆栈的情况下完成迭代或增长堆栈，因为第一次调用不在尾部位置并且始终具有延续。

简单的斐波那契、快速排序和树的总和都属于这一类。