algorithm - 是否存在不可避免的使用堆栈帧的递归函数/算法（不能完全尾递归）？

Question

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

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

Answer 1

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

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