algorithm - Quicksort的尾叫优化

我刚刚进入TCO，我理解它如何重用单个堆栈帧的概念，而不是每次方法调用自己时创建一个新的堆栈帧。我直观地想将这个结构与while循环进行比较，因为循环将持续对一组变量执行操作，直到条件不满足为止。
然而，考虑到TCO只使用一个堆栈帧，似乎不可能执行排序算法，例如quicksort，使用TCO作为堆栈帧的引用，一旦达到基本情况，递归方法“展开”备份调用堆栈，就需要执行排序算法如果不引用方法被调用的次数，它如何知道要执行哪个后续操作以及执行多少次？
假设每个调用的方法体都是相同的，我想它可以只保留对方法被调用次数的引用，然后在方法体中保留一个指针，指示从哪里开始执行，但这只是一个猜测。
谢谢你的帮助。

最佳答案

每当递归调用处于最终位置时，都可以执行TCOquicksort需要两个递归调用，很明显它们不能都在那个位置，但是其中一个可以，所以尾部调用可以转换为while循环：
原件（伪码）：

quicksort(i, j) {
    return if j <= i
    k = getPivot(i, j)
    partition(i, j, k)
    quicksort(i, k-1)    <--- This recursive call can't be changed
    quicksort(k+1, j)    <--- This recursive call is amenable to TCO
}

TCO之后：

quicksort(i, j) {
    while (j > i) {
        k = getPivot(i, j)
        partition(i, j, k)
        quicksort(i, k-1)    <--- This recursive call is unchanged
        i = k+1
    }
}

按相反的顺序调用它们也可以。

关于algorithm - Quicksort的尾叫优化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28097179/