快速排序和尾部递归优化 [英] Quicksort and tail recursive optimization

问题描述

在算法简介 p169讨论了对Quicksort使用尾递归.

In Introduction to Algorithms p169 it talks about using tail recursion for Quicksort.

本章前面的原始Quicksort算法是(用伪代码)

The original Quicksort algorithm earlier in the chapter is (in pseudo-code)

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

使用尾部递归的优化版本如下

The optimized version using tail recursion is as follows

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

Partition在其中根据轴对数组进行排序.

Where Partition sorts the array according to a pivot.

区别在于第二种算法仅调用Quicksort一次即可对LHS进行排序.

The difference is that the second algorithm only calls Quicksort once to sort the LHS.

有人可以向我解释为什么第一种算法会导致堆栈溢出，而第二种却不会吗?还是我误会了这本书?

Can someone explain to me why the 1st algorithm could cause a stack overflow, whereas the second wouldn't? Or am I misunderstanding the book.

推荐答案

首先让我们从一个简单的，可能不准确但仍然有效的堆栈溢出定义开始.

First let's start with a brief, probably not accurate but still valid, definition of what stack overflow is.

您现在可能已经知道，有两种不同类型的内存以太不同的数据结构实现:堆和堆栈.

As you probably know right now there are two different kind of memory which are implemented in too different data structures: Heap and Stack.

就大小而言，堆大于堆栈，为简单起见，假设每次调用函数时，都会在堆栈上创建一个新的环境(局部变量，参数等).因此，鉴于这种情况，并且堆栈的大小受到限制，因此，如果您进行太多的函数调用，则会用完空间，从而导致堆栈溢出.

In terms of size, the Heap is bigger than the stack, and to keep it simple let's say that every time a function call is made a new environment(local variables, parameters, etc.) is created on the stack. So given that and the fact that stack's size is limited, if you make too many function calls you will run out of space hence you will have a stack overflow.

递归的问题在于，由于每次迭代都在堆栈上创建至少一个环境，因此您将很快在有限的堆栈中占用大量空间，因此堆栈溢出通常与递归调用相关.

The problem with recursion is that, since you are creating at least one environment on the stack per iteration, then you would be occupying a lot of space in the limited stack very quickly, so stack overflow are commonly associated with recursion calls.

因此有一种称为"Tail递归调用优化"的东西，它将在每次进行递归调用时重用相同的环境，因此堆栈中的空间是恒定的，从而防止了堆栈溢出问题.

So there is this thing called Tail recursion call optimization that will reuse the same environment every time a recursion call is made and so the space occupied in the stack is constant, preventing the stack overflow issue.

现在，有一些规则可以执行尾部调用优化.首先，每个调用最完整，也就是说，如果您中断执行，该函数应该能够在任何时候给出结果，请参见

Now, there are some rules in order to perform a tail call optimization. First, each call most be complete and by that I mean that the function should be able to give a result at any moment if you interrupts the execution, in SICP this is called an iterative process even when the function is recursive.

如果您分析第一个示例，您将看到每个迭代均由两个递归调用定义，这意味着如果您随时停止执行，将无法给出部分结果，因为结果取决于这些要完成的调用中，在这种情况下，您无法重用堆栈环境，因为总的信息分配在所有这些递归调用中.

If you analyze your first example, you will see that each iteration is defined by two recursive calls, which means that if you stop the execution at any time you won't be able to give a partial result because you the result depends of those calls to be finished, in this scenario you can't reuse the stack environment because the total information is split between all those recursive calls.

但是，第二个示例没有这个问题，A是常数，并且p和r的状态可以本地确定，因此，由于所有要保持的信息都存在，因此可以应用TCO.

However, the second example doesn't have that problem, A is constant and the state of p and r can be locally determined, so since all the information to keep going is there then TCO can be applied.

这篇关于快速排序和尾部递归优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！