algorithm - 快速排序的尾调用优化

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
}

总拥有成本之后:

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

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