快速排序的尾部调用优化

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
    }
}

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