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

问题描述

在算法简介 p169 它谈到了对 Quicksort 使用尾递归.

In Introduction to Algorithms p169 it talks about using tail recursion for 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.

谁能向我解释为什么第一个算法会导致堆栈溢出，而第二个不会?或者我误解了这本书.

推荐答案

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

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.

所以有一种叫做尾递归调用优化的东西，每次进行递归调用时都会重用相同的环境，因此堆栈中占用的空间是恒定的，防止堆栈溢出问题.

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.

现在，有一些规则可以执行尾调用优化.首先，每个调用都是完整的，我的意思是如果您中断执行，该函数应该能够随时给出结果，在 SICP即使函数是递归的，这也被称为迭代过程.

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屋！