快速排序的尾调用优化

Question

我刚刚进入 TCO，我了解它如何重用单个堆栈框架而不是每次方法调用自身时创建一个新堆栈框架的概念。我直觉地想将此结构与while循环进行比较，因为循环将不断对一组变量执行操作，直到不满足条件为止。

但是，鉴于 TCO 仅使用一个堆栈帧，似乎一旦递归方法“展开”一次调用堆栈，就需要使用 TCO 作为对堆栈帧的引用来执行诸如快速排序之类的排序算法达到了基本情况。没有引用该方法被调用的次数，它怎么知道接下来要执行哪个操作以及执行多少次呢？

鉴于每次调用的方法主体是相同的，我猜它可以只保留对方法被调用次数的引用，然后是方法主体内开始执行位置的指针，但这只是一个猜测。

谢谢你的帮助。

Answer 1

只要递归调用处于最终位置，就可以执行 TCO。快速排序需要两个递归调用，所以显然不能都在那个位置-但他们中的一个就可以了，所以这尾调用可以转换为一个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
    }
}

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