第一章

CHAPTER 1: INTRODUCTION

第一章:简介

In this chapter, we discuss the aims and goals ofthis text and briefly review programming concepts and discrete mathematics. Wewill

此章，我们将讨论本书目的并且简单温故一下编程思想和离散数学.我们将

[if !supportLists]l  [endif]See that how a program performs for reasonably large input is just asimportant as its performance on moderate amounts of input.

    领会一个程序在多输入条件下是如何执行与它在输入量适当的条件下如何执行同等重要

[if !supportLists]l  [endif]Review good programming style.

    温故一下良好的编程风格

[if !supportLists]l  [endif]Summarize the basic mathematical background needed for the rest of thebook.

    总结本书使用到的必备数学基础

[if !supportLists]l  [endif]Briefly review recursion.

    简单地复习一下递归

1.1. What's the Book About?

1.1关于本书*

Suppose you have a group of n numbers andwould like to determine the kth largest. This is known as the selectionproblem. Most students who have had a programming course or two would have nodifficulty writing a program to solve this problem. There are quite a few"obvious" solutions.

假设你有个n个数字的数组并且想要确认一下第k个比较大数值。这被称为选择问题。很多学过一两门编程课程的同学可以轻而易举地写个程序解决这个问题。有很多的解决方法。

One way to solve this problem would be toread the n numbers into an array, sort the array in decreasing order by somesimple algorithm such as bubblesort, and then return the element in position k.

一种解决这个问题的方式是把这n个数字放到一个数组里面，通过一些简单的算法(例如冒泡排序)将这个数组进行递减排序，然后返回第K个位置的元素

A somewhat better algorithm might be toread the first k elements into an array and sort them (in decreasing order).Next, each remaining element is read one by one. As a new element arrives, itis ignored if it is smaller than the kth element in the array. Otherwise, it isplaced in its correct spot in the array, bumping one element out of the array.When the algorithm ends, the element in the kth position is returned as theanswer.

一个更好的速算法是将前K个元素读入一个数组里面并将其排序(递减排序序列)。下来，剩下的元素一个一个的访问。每访问一个新元素，如果他比原先数组中的第k位元素素小的话就忽略它，否则将此元素替换到数组中的合适的位置。当算法结束时，第k个元素将作为答案被返回。

Both algorithms are simple to code, and youare encouraged to do so. The natural questions, then, are which algorithm isbetter and, more importantly, is either algorithm good enough? A simulationusing a random file of 1 million elements and k = 500,000 will show thatneither algorithm finishes in a reasonable amount of time--each requiresseveral days of computer processing to terminate (albeit eventually with acorrect answer). An alternative method, discussed in Chapter 7, gives asolution in about a second. Thus, although our proposed algorithms work, theycannot be considered good algorithms, because they are entirely impractical forinput sizes that a third algorithm can handle in a reasonable amount of time.

两个算法编写起来都很简单，你应该去实践一下。那么一个白痴的问题来了，那个算法更好？进一步再说，这个相对好一点的算法它地的确确足够好么？一个有使用1百万个元素并且K=50万的随机文档的模拟问题将显示任何一个算法都无法在一个合理的时间内完成--每个(算法)都需要数天的实践来计算才能结束。（虽然确实在最后能得出正确答案）,在第七章讨论了一个可供选择的方法，它一秒就可以得出答案。因此，虽然我们提出的算法的确能哟on个，但是它们称不上是好算法，因为第三个算法可以在可靠时间内处理的输入规模对它们两而言，实现起来完全不切实际。

A second problem is to solve a popular wordpuzzle. The input consists of a two-dimensional array of letters and a list ofwords. The object is to find the words in the puzzle. These words may behorizontal, vertical, or diagonal in any direction. As an example, the puzzleshown in Figure 1.1 contains the words this, two, fat, and that. The word thisbegins at row 1, column 1 (1,1) and extends to (1, 4); two goes from (1, 1) to(3, 1); fat goes from (4, 1) to (2, 3); and that goes from (4, 4) to (1, 1).

第二个问题是解决一个众数单词问题。输入是由一个二维字母数组和一列单词组成的。目的是在问题中找出众数单词。这些单词或水平或竖直或对角的任意方向。举个栗子，如图1.1所示，该图包含了单词this，two，fat，and that。This这个单词从(1,1)延伸到(1,4);Two 从(1,1)延伸到(3,1)；Fat从(4,1)到(2,3);That从(4,4)到(1,1)。

Again, there are at least twostraightforward algorithms that solve the problem. For each word in the wordlist, we check each ordered triple (row, column, orientation) for the presenceof the word. This amounts to lots of nested for loops but is basicallystraightforward.

另外，至少有两种明显的算法可以解决这个问题。对于每个单词列表中的单词而言，我们检查有序的三个(方向)确认是否存在单词。这就相当于是基于直线的多层嵌套循环。

Alternatively, for each ordered quadruple(row, column, orientation, number of characters) that doesn't run off an end ofthe puzzle, we can test whether the word indicated is in the word list. Again,this amounts to lots of nested for loops. It is possible to save some time ifthe maximum number of characters in any word is known.

再者，对于每个四次序列（行，列，斜向，字符数）检索而言，它不能很快写出这个问题的结果，我们可以检测是否这个单词在这个单词表中。也就是说，这就相当于是多层嵌套循环。如果每个单词中出现的最多的字母是提前预知的，就可能节省一些时间。

It is relatively easy to code up eithersolution and solve many of the real-life puzzles commonly published in magazines.These typically have 16 rows, 16 columns, and 40 or so words. Suppose, however,we consider the variation where only the puzzle board is given and the wordlist is essentially an English dictionary. Both of the solutions proposedrequire considerable time to solve this problem and therefore are notacceptable. However, it is possible, even with a large word list, to solve theproblem in a matter of seconds.

编码上述任意一个解决方案并且解决许多出版杂志中普遍出现的现实的问题相对来说是容易的。这些通常有16行，16列，大约40个单词。然而，假设我们考虑到这种情况，仅仅给定问题的图案，并且这个单词表实际上就是一本英语辞典。这两个解决方案都需要很大的时间解决这个问题，这一点是让人无法忍受的。然而，即使是一个很大的单词列表，用几秒钟的时间解决这个问题也是可能的。

An important concept is that, in manyproblems, writing a working program is not good enough. If the program is to berun on a large data set, then the running time becomes an issue. Throughoutthis book we will see how to estimate the running time of a program for largeinputs and, more importantly, how to compare the running times of two programswithout actually coding them. We will see techniques for drastically improvingthe speed of a program and for determining program bottlenecks. Thesetechniques will enable us to find the section of the code on which toconcentrate our optimization efforts.

一个重要的思想是，在许多问题中没有完美的工作程序。如果程序在一个大的数据集合上，运行时间就变成了一个大问题。怎样去估计一个大输入程序的运行时间这个问题贯穿了整本书。更重要的是比较两个还没有实际编码的程序的运行时间。我们将会学习到大幅度提高程序运行速度的技术以及测定程序的瓶颈的技术。这些技术可以使我们找出我们应该集中精力去优化的那些代码片段。

[if !vml]

[endif]

Figure 1.1 Sample word puzzle

 

 

1.2. Mathematics Review

1.2.数学复习

      This section lists some of the basic formulas you need to memorize or beable to derive and reviews basic proof techniques.

      这一部分列出了一些你需要记住的或者是导出的基础数学公式并且复习基础的证明方法。

1.2.1. Exponents

1.2.1指数

[if !vml]

[endif]

1.2.2.Logarithms

1.2.2.Logarithms

      In computer science, alllogarithms are to base 2 unless specified otherwise.

     在计算机科学中，所有的对数都是以2为底数的除非有特殊声明。

DEFINITION:[if !vml]

[endif] if and only if[if !vml]

[endif]

定义：[if !vml]

[endif]当且仅当[if !vml]

[endif]

 Severalconvenient equalities follow from this definition.

 通过这个定义可以推导出几个便利的公式

THEOREM 1.1.

定理1.1.

PROOF:

 [if !vml]

[endif]

证明：

      Let[if !vml]

[endif], and[if !vml]

[endif]. Then, by the definition oflogarithms,[if !vml]

[endif], and[if !vml]

[endif]. Combining these three equalitiesyields[if !vml]

[endif]. Therefore, x = yz, which implies z =x/y, proving the theorem.

       令[if !vml]

[endif], 和[if !vml]

[endif]。那么，通过给出的对数的定义，[if !vml]

[endif], and[if !vml]

[endif]。结合这三个等式可以推导出[if !vml]

[endif]。因此，x = yz，那么z = x/y，定理由此可证。

THEOREM 1.2.

定理1.2.

log ab = log a + log b

PROOF:

证明：

     Letx = log a, y = log b, z = log ab. Then, assuming the default base of 2,[if !vml]

[endif]. Combining the last three equalitiesyields[if !vml]

[endif]. Therefore,x + y

= z, which proves the theorem.

    令x = log a, y = log b, z = log ab。默认底数为2，[if !vml]

[endif]。结合后边这三个等式[if !vml]

[endif]，则x + y = z，由此定理可证。

    Someother useful formulas, which can all be derived in a similar manner, follow.

   下面这些有用的公式，都可以用相似的方法推导。

  [if !vml]

[endif]

1.2.3. Series

1.2.3.级数

The easiest formulas to remember are

[if !vml]

[endif]

and the companion,

[if !vml]

[endif]

要记住的最简单的公式是[if !vml]

[endif]类似的[if !vml]

[endif]。

     In the latterformula, if 0 < a < 1, then[if !vml]

[endif]and as n tends to [if !vml]

[endif], the sum approaches 1/(1 -a). These are the

"geometric series" formulas.We can derive the last formula for[if !vml]

[endif]in the following manner. Let S be the sum.

Then[if !vml]

[endif]

Then[if !vml]

[endif]

       接下来，如果0 < a < 1,那么[if !vml]

[endif]，并且当n趋向于[if !vml]

[endif]时，结果无限接近1/(1 -a)。这些是“等比级数”公式。我们就可以用下面的方法导出最后的公式[if !vml]

[endif]。把这个总和记为S，

那么[if !vml]

[endif]，那么[if !vml]

[endif]

     If we subtract thesetwo equations (which is permissible only for a convergent series), virtuallyall the terms on the right side cancel, leaving[if !vml]

[endif]which simplies that[if !vml]

[endif]We can use this same technique to compute[if !vml]

[endif], a sum that occurs frequently. Wewrite[if !vml]

[endif]and multiply by 2, obtaining

[if !vml]

[endif]。Subtracting these two equations yields[if !vml]

[endif]。Thus, S = 2.

    如果这两个等式相减（只允许是收敛级数时），右边所有项几乎都消去了，剩下了[if !vml]

[endif],就简化成了[if !vml]

[endif]我们可以使用相同的方法计算多项式[if !vml]

[endif]的和，我们写成[if !vml]

[endif]，等式乘以二可得[if !vml]

[endif]，等式两边相减得到[if !vml]

[endif]，可得S = 2。

     Another type ofcommon series in analysis is the arithmetic series. Any such series can beevaluated from the basic formula.

[if !vml]

[endif]

     在分析里边另外一个常见级数类型是算法级数。任一个这样的级数都能用基础的公式[if !vml]

[endif]计算。

     For instance, to findthe sum 2 + 5 + 8 +. . . + (3k - 1), rewrite it as 3(1 + 2+ 3 +. . . + k) - (1+ 1 + 1 +. . . + 1), which is clearly 3k(k + 1)/2 - k. Another way to rememberthis is to add the first and last terms (total 3k + 1), the second and next tolast terms (total 3k + 1), and so on. Since there are k/2 of these pairs, thetotal sum is k(3k + 1)/2, which is the same answer as before.

     例如，为了计算2 + 5 + 8 +. . . + (3k - 1)的和，把它改写成3(1 + 2+

3 +. . . + k) - (1 + 1 + 1 +. . . + 1)，就等于3k(k + 1)/2 -

k。另外一个记住这个的方法就是首尾相加（和为3k + 1），第二项和倒数第二项相加（和为3k + 1），等等。有这样k/2对，总和就是k(3k + 1)/2，跟之前的答案相同。

     The next two formulaspop up now and then but are fairly infrequent.

[if !vml]

[endif]

When k = -1, the latter formula is not valid. We then need thefollowing formula, which is used far more in computer science than in othermathematical disciplines. The numbers, HN, are known as the harmonic numbers,and the sum is known as a harmonic sum.The error in the

following approximation tends to y[if !vml]

[endif] 0.57721566, which is known asEuler's constant.

[if !vml]

[endif]

     下面两个几乎用不到的公式我们也列举出来：

[if !vml]

[endif]

当k=-1时，后边这个公式没有意义。我们需要后边这个公式，它在计算机科学中比在其他数学科目中用得多得多。这个数列被称为调和数列，这个和被称为调和级数之和。下边这个近似值的误差趋近于y[if !vml]

[endif] 0.57721566，这被称作欧拉常量。

These two formulas are just general algebraic manipulations.

[if !vml]

[endif]

下边这两个公式就是常见的代数运算：

[if !vml]

[endif]

1.2.4. Modular Arithmetic

1.2.4.模数运算

     We saythat a is congruent to b modulo n, written a[if !vml]

[endif]b(mod n), if n divides a - b.Intuitively, this means that the remainder is the same when either a or b isdivided by n. Thus, 81 61 1(mod 10). As with equality, if a b (mod n), then a +c b + c(mod n) anda d b d (mod n).

     我们说a恒等于b对n求模，写成a≡b(mod n)(a同余于b模n，或读作a与b关于模m同余），如果n能整除a-b。直观地说，意思就是当a或b被n除的时候，它们的余数相同。例如， 81 61 1(mod 10)。等价的，如果 a b (mod n)，那么a + c b + c(mod n)和a d b d (mod n)。

There are a lot of theorems that apply to modulararithmetic, some of which require extraordinary proofs in number theory. Wewill use modular arithmetic sparingly, and the preceding theorems will suffice.

有很多适用于模数运算的定理，有些在数论中证明的很巧妙。我们用到模数运算不多，前面的那些定理就够用了。

1.2.5. The P Word

1.2.5.证明方法

     The twomost common ways of proving statements in data structure analysis are proof byinduction and proof by contradiction (and occasionally aproof

by intimidation, by professors only). The best way of proving that atheorem is false is by exhibiting a counterexample.

     数据结构中两个最常见的证明方法是归纳证明法和反证法（只有教授偶尔使用归谬法）。证明一个定理错误的最好的方法是举反例。

Proof byInduction

归纳法证明

A proofby induction has two standard parts. The first step is proving a base case,that is, establishing that a theorem is true for some small (usuallydegenerate) value(s); this step is almost always trivial. Next, an inductivehypothesis is assumed. Generally this means that the theorem is assumed to betrue for all cases up to some limit k. Using this assumption, the theorem isthen shown to be true for the next value, which is typically k + 1. This provesthe theorem (as long as k is finite).

归纳法证明由标准的两步构成。第一步是证明基本的情况，确定一个定理对一小部分值成立；这一步是琐细的。下一步，一个归纳的假设是假定的。通常情况下这就意味着到k为止的所有情况下假设都是成立的。使用这个假设，证明接下来的k+1值对于这个假设也是成立的。定理可证（只要k是有限的）。

     As anexample, we prove that the Fibonacci numbers,[if !vml]

[endif]satisfy[if !vml]

[endif]。(Some definitions have F0 = 0, which

shifts the series.) To do this, we first verify that the theorem is true for

the trivial cases.It is easy to verify that F1 = 1 < 5/3 and F2 = 2。We assume that the theorem is true for i = 1, 2, . . . , k; this is

the inductive hypothesis. To prove the theorem, we need to show that[if !vml]

[endif]。We have[if !vml]

[endif]，by the definition, and we can use theinductive hypothesis on the right-hand side, obtaining

   [if !vml]

[endif]

[if !vml]

[endif]

which simplifies to

[if !vml]

[endif]

proving the theorem.

      举个例子，我们证明斐波那契数列，[if !vml]

[endif]，满足[if !vml]

[endif]。（有一些定义改变了这个数列，设置了F0=0）。为了这名这个定理，我们首先证明这个定理适用于琐细的情况。证明F1 = 1 < 5/3 和F2 = 2是简单的。我们假设这个定理适用于i = 1, 2, . . . , k；这是归纳假设。为了证明这个定理，我们需要证明[if !vml]

[endif]（1是加于k上的）。我们有[if !vml]

[endif]，通过定义，我们把这个归纳假设用在等号右边，得到

[if !vml]

[endif]

[if !vml]

[endif]

化简为

[if !vml]

[endif]

定理可证。

     As asecond example, we establish the following theorem.

     第二个例子，我们证明下一个定理。

THEOREM 1.3.

[if !vml]

[endif]

当[if !vml]

[endif]

PROOF:

证明：

     Theproof is by induction. For the basis, it is readily seen that the theorem istrue when n = 1. For the inductive hypothesis, assume that the theorem is truefor[if !vml]

[endif]. We will establish that, underthis assumption, the theorem is true for n + 1. We have

[if !vml]

[endif]

Applying the inductive hypothesis, we obtain

[if !vml]

[endif]

Thus,

[if !vml]

[endif]

proving the theorem.

   用归纳法证明。首先，当n=1时，定理显然成立。假设这个定理对于[if !vml]

[endif]都是成立的。我们将证明这个定理在这个假设的情况下对于n+1也是成立的。我们有

[if !vml]

[endif]

根据这个归纳假设，可以得到

[if !vml]

[endif]

因此，

[if !vml]

[endif]

Proof by Counterexample

举反例法证明

     Thestatement[if !vml]

[endif]is false.The easiest way to prove

this is to compute[if !vml]

[endif]。

          [if !vml]

[endif]是错误的。最简单的证明方法就是估计[if !vml]

[endif]。

Proof by Contradiction

反证法

     Proof bycontradiction proceeds by assuming that the theorem is false and showing thatthis assumption implies that some known property is false, and hence theoriginal assumption was erroneous. A classic example is the proof that there isan infinite number of primes. To prove this, we assume that the theorem isfalse, so that there is some largest prime[if !vml]

[endif]，Let[if !vml]

[endif]be all the primes in order and

consider[if !vml]

[endif]。Clearly, N is larger than pk, so byassumption N is not prime. However, none ofp1, p2, . . . ,

pkdivide N exactly, because there will always be a remainder of 1. This isa contradiction, because every number is either prime or a product of primes.Hence, the original assumption, that pk is the largest prime, is false, whichimplies that the theorem is true.

[if !vml]

[endif]

       反证法通过假设这个定理是错的来进行的，证明这个假设就意味着证明一些已知条件是错的，从而假设是错误的。一个典型的例子就是证明有无穷多个质数。为了证明，我们假设这个定理是错误的，所以就有最大的质数[if !vml]

[endif]，使得[if !vml]

[endif]是按顺序排列的所有的质数并且令[if !vml]

[endif]。很明显，N比pk大，所以根据假设，N不是质数。事实上，p1, p2, . . . , pk没有一个数能整除N，因为总有一个余数1.这就是反证，因为每一个数都是质数或者质数的乘积。因此，最初的假设：pk是最大的质数是错误的，证明了定理是正确的。

1.3. A Brief Introduction to Recursion

1.3. 递归的简介

Most mathematical functions that we arefamiliar with are described by a simple formula. For instance, we can converttemperatures from Fahrenheit to Celsius by applying the formula

我们熟悉的绝大多数数学函数都可以使用一个简单的数学公式来表达。举个栗子，我们可以通过下述公式将温度值从华氏度转化为是摄氏度

 C =5(F - 32)/9

摄氏度=5x(华氏度-32)/9

Given this formula, it is trivial to writea C function; with declarations and braces removed, the one-line formulatranslates to one line of C.

给出的这个公式，如果用C函数写出来小菜一碟；如果不考虑声明和括号，单句公式可以被翻译成一句C语言语句。

Mathematical functions are sometimesdefined in a less standard form. As an example, we can define a function f,valid on nonnegative integers, that satisfies f(0) = 0 and f(x) = 2f(x - 1) +x2. From this definition we see that f(1) = 1, f(2) = 6, f(3) = 21, and f(4) =58. A function that is defined in terms of itself is called recursive. C allowsfunctions to be recursive.

有时,数学公式是使用极简形式。举个栗子,我们可以定义一个函数f,定义域为非负整数，满足f(0)=0,且f（x）=2f(x-1)+x^2。从此定义我们可以得出，f(1) = 1, f(2) = 6, f(3)

= 21, f(4) = 58。一个函数是根据自身定义的，那么这个函数就是递归的。C语言允许递归。

* It is important to remember that what Cprovides is merely an attempt to follow the recursive spirit. Not allmathematically recursive functions are efficiently (or correctly) implementedby C's simulation of recursion. The idea is that the recursive function f oughtto be expressible in only a few lines, just like a non-recursive function.Figure 1.2 shows the recursive implementation of f.

谨记C语言仅提供一个试图遵循递归性是重要的。并非所有的数学递归函数都能用C语言有效(或合适)地实现。思想是递归函数f应当像非递归函数一行可以仅用几行代码描述出来.

图片1.2显示了递归函数f的实现

*Using recursion for numerical calculationsis usually a bad idea. We have done so to illustrate the basic points. Lines 1and 2 handle what is known as the base case, that is, the value for which thefunction is directly known without resorting to recursion. Just as declaringf(x) = 2 f(x - 1) + x2 is meaningless, mathematically, without including thefact that f (0) = 0, the recursive C function doesn't make sense without a basecase. Line 3 makes the recursive call.

使用递归计算数值通常不是什么好想法。我们先表明了基础态度。第一二行代码已经处理了元情况，也就是说，此函数的值无需递归计算，直接给出。就像声明数学函数f(x) = 2 f(x - 1) + x^2在不给定能够基础条件f（0）=0下是无意义的一样。该C语言递归函数在无元情况条件下也是无意义的。第三行代码使用了递归调用。

There are several important and possiblyconfusing points about recursion. A common question is: Isn't this justcircular logic? The answer is that although we are defining a function in termsof itself, we are not defining a particular instance of the function in termsof itself. In other words, evaluating f(5) by computing f(5) would be circular.Evaluating f(5) by computing f(4) is not circular--unless, of course f(4) isevaluated by eventually computing f(5). The two most important issues areprobably the how and why questions. In Chapter 3, the how and why issues areformally resolved. We will give an incomplete description here.

关于递归，有以下几个重难点。一个经常遇到的问题就是:递归就是一个逻辑循环吗？答案是:虽然我们使用函数本身来定义它自己，但是我们并未定义一个特定的函数实例。换句话说，使用计算机计算f(5)的值就是循环，通过f(4)的值来计算f(5)不是循环----当然，这不包括f(4)的值在计算f(5)的过程中已经计算出来的这种情况。两个最重要的点或许是问题怎样破和为什么这么破。在第三章中，这两点会正式解决。我们在这里给一个不完整的描述。

It turns out that recursive calls arehandled no differently from any others. If f is called with the value of 4,then line 3 requires the computation of 2 * f(3) + 4 * 4. Thus, a call is madeto compute f(3). This requires the computation of 2 * f(2) + 3 * 3. Therefore,another call is made to compute f(2). This means that 2 * f(1) + 2 * 2 must beevaluated. To do so, f(1) is computed as 2 * f(0) + 1 * 1. Now, f(0) must beevaluated. Since this is a base case, we know a priori that f(0) = 0. Thisenables the completion of the calculation for f(1), which is now seen to be 1.Then f(2), f(3), and finally f(4) can be determined. All the bookkeeping neededto keep track of pending function calls (those started but waiting for arecursive call to complete), along with their variables, is done by thecomputer automatically. An important point, however, is that recursive callswill keep on being made until a base case is reached. For instance, anattempt to evaluate f(-1) will result in calls to f(-2), f(-3), and so on.Since this will never get to a base case, the program won't be able to computethe answer (which is undefined anyway). Occasionally, a much more subtle erroris made, which is exhibited in Figure 1.3. The error in the program in Figure1.3 is that bad(1) is defined, by line 3, to be bad(1). Obviously, thisdoesn't give any clue as to what bad(1) actually is. The computer will thusrepeatedly make calls to bad(1) in an attempt to resolve its values.Eventually, its bookkeeping system will run out of space, and the program willcrash. Generally, we would say that this function doesn't work for one specialcase but is correct otherwise. This isn't true here, since bad(2) calls bad(1).Thus, bad(2) cannot be evaluated either. Furthermore, bad(3), bad(4), andbad(5) all make calls to bad(2). Since bad(2) is unevaluable, none of thesevalues are either. In fact, this program doesn't work for any value of n,except 0. With recursive programs, there is no such thing as a "specialcase."

执行递归调用和执行其他调用时没啥区别的！如果使用参数值为4调用函数f,那么第三行代码要求计算2*f(3)+4*4。因此，产生了一个新的调用来计算f(3)。这个新的调用要求去计算2*f(2)+3*3.因此再来一个调用来计算f(2),这就相当于会计算2*f(1)+2*2,为了完成这个计算f(1)会被计算为2f(0)+1*1。现在,f(0)一定要被计算出来了。因为这是一个源情况,我们知道原条件f(0)=0。这就是的f(1)可以被计算了，f(1)=1,以此类推,f(2),f(3),最终f(4)都可以被计算出。所有根据路径被记在账本上的待定的函数调用伴随着他们的变量值都被电脑自动计算了。然而，在抵达元情况之前,递归调用将一直在重复是个重点。举个例子，尝试计算f(-1)将导致调用计算f(-2),f(-3)等等...。程序将无法计算算出答案(它们未定义),因为它永远无法到达元情况。偶尔，展示出的图片1.3会产生一个坑人于无形的错误。图1.3中程序的错误在求bad(1)在第三行代码产生了。

明显，关于bad(1)实际上是啥，它等于没说！电脑会重复调用去尝试计算算bad(1)的值。最后，这个记账本系统将会使用完所有的空间，并且程序会崩溃。一般而言呢，我们会说这个函数在特定条件下不工作但其余情况运转正常。它在这儿这儿不对，bad(2)要调用bad(1)，因此，bad(2)也是无法计算的，此外，bad(3),bad(4)，bad(5)都会调用bad(2)，因为bad(2)无法计算，因此他们没有一个可以倍计算出来。事实上，这个程序对于任意的非零n,都无法正常工作。对于递归程序而言，没有什么”特殊情况”！

These considerations lead to the first twofundamental rules of recursion:

关于递归,这有两个基本原则值得考虑:

[if !supportLists]1. [endif]Base cases.You must always have some base cases, which can be solved without recursion.

[if !supportLists]1.[endif]元情况，你必须总有一些不适用递归就能得出答案的基本情况

[if !supportLists]2. [endif]Makingprogress. For the cases that are to be solved recursively, the recursive callmust always be to a case that makes progress toward a base case.

[if !supportLists]2.[endif]编写下一步。对于那些使用递归解决的情况而言，递归调用必须总是达到一种可以逐步使用到元情况的状态。

Throughout this book, we will use recursionto solve problems. As an example of anonmathematical use,consider a large dictionary. Words in dictionaries are defined in terms ofother words. When we look up a word, we might not always understand thedefinition, so we might have to look up words in the definition. Likewise, wemight not understand some of those, so we might have to continue this searchfor a while. As the dictionary is finite, eventually either we will come to apoint where we understand all of the words in some definition (and thusunderstand that definition and retrace our path through the other definitions),or we will find that the definitions are circular and we are stuck, or thatsome word we need to understand a definition is not in the dictionary.

我们递归地解决遇到的问题将贯穿整本书。对于那些非数学的用例，将它们人做是一个超大的字典。字典中的单词使用其他单词来定义。当我们查询一个单词的时候，我们或许不总是理解其定义，因此我们可能要查询其定义中的单词。同样，我们或许不理解它们(定义中的单词)，因此我们不得不继续再进行查找。因为一个字典是有限的，要么最终我们可以抵达理解定义中所有的单词的地步(理解那些定义并且回溯我们对单词的理解路径)，要么我们会发现我们卡在轮回的定义上，要么我们需要理解的某些单词定义根本不在字典里。

[if !vml]

[endif]

图1.3  一个无尽的递归程序

Our recursive strategy to understand wordsis as follows: If we know the meaning of a word, then we are done; otherwise,we look the word up in the dictionary. If we understand all the words in thedefinition, we are done; otherwise, we figure out what the definition means byrecursively looking up the words we don't know. This procedure will terminateif the dictionary is well defined but can loop indefinitely if a word is eithernot defined or circularly defined.

我们理解单词递归策略如下:如果我们知道一个单词的意思，那么就罢了，否则，我们需要在字典中查询。如果我们理解定义中的所有单词，那就完成了，否则，我们需要通过递归查询那些我们不懂得单词来搞明白定义。如果字典编写的很好,那么这个套路结束了，如果一个单词没定义或轮回定义,那么这个套路就没完没了了。

Printing Out Numbers

打印数字

Suppose we have a positive integer, n, thatwe wish to print out. Our routine will have the heading print_out(n). Assumethat the only I/O routines available will take a single-digit number and outputit to the terminal. We will call this routine print_digit; for example,print_digit(4) will output a 4 to the terminal.

假设我们想打印一个正数，我们的程序把 print_out(n)作为标题,假设唯一I/O程式可用将取一个个位数取出并显示在终端上。我们将这个程式成为print_digit;比如来说，print_digit(4)，就是把4输出到终端上。

Recursion provides a very clean solution tothis problem. To print out 76234, we need to first print out 7623 and thenprint out 4. The second step is easily accomplished with the statementprint_digit(n%10), but the first doesn't seem any simpler than the originalproblem. Indeed it is virtually the same problem, so we can solve itrecursively with the statement print_out(n/10).

对于这个问题，递归给出一个极简风格的解决方案。为了打印出76234，我们需要先打印7623而后打印4.第二步通过表达式print_digit(n%10)非常容易实现，但是前面的部分看起来似乎不必原问题简单。的确它是相同的问题,因此我们通过表达式print_out(n/10)来递归的解决它们。

This tells us how to solve the generalproblem, but we still need to make sure that the program doesn't loopindefinitely. Since we haven't defined a base case yet, it is clear that we stillhave something to do. Our base case will be print_digit(n) if 0

这给我们说明了如何解决一般问题，但是我们仍需确认这个程序不会无限循环。因为我们仍未定义元情况，明显我们还有些事情未做。我们的元情况就是print_digit(n) if 0

* is shown Figure 1.4.

已经在图1.4中给出。

*The term procedure refers to a functionthat returns void.

这个部分程序是无返回值函数

We have made no effort to do thisefficiently. We could have avoided using the mod routine (which is veryexpensive) because n%10 = n - (n/10) * 10.

我们轻易地已经完成了这个程序。我们本可以避免使用模数例程(模数运算太高消耗)，因为 n%10求余 = n-(n/10)*10。

Recursion and Induction

递归和归纳

Let us prove (somewhat) rigorously that therecursive number-printing program works. To do so, we'll use a proof byinduction.

让我们严格证明递归数字打印程序。为此，我们需要使用归纳来证明。

THEOREM 1.4

定理1.4

The recursive number-printing algorithm iscorrect for n >=0.

对于n>=0的情况，这个递归打印数字算法是正确的。

PROOF: First, if n has one digit, then theprogram is trivially correct, since it merely makes a call to print_digit.Assume then that print_out works for all numbers of k or fewer digits. A numberof k + 1 digits is expressed by its first k digits followed by its leastsignificant digit. But the number formed by the first k digits is exactly n/10, which, by the indicated hypothesis is correctly printed, and the last digitis n mod10, so the program prints out any (k + 1)-digit number correctly. Thus,by induction, all numbers are correctly printed.

证明:首先，如果n是个位数字，那么很简单，它是正确的，因为他只调用了跑一次print_digit。假设print_out支持k个或少于k数位的数字作为参数。一个k+1位数字就是由它的前k位数字和在这之后的最低有效位数字组成。但是前k位数字组成的书实际上等于n/10,根据之前的假设它们(前k个数字组成的数)可以被正确打印,并且最后一位数就是n mod 10,因此这个程序可以正确打印任意(k+1)位的数字。因此，通过归纳法，所有的数字都可以被正确打印。

[if !vml]

[endif]

图片1.4 递归程序打印一个整数

This proof probably seems a little strangein that it is virtually identical to the algorithm description. It illustratesthat in designing a recursive program, all smaller instances of the sameproblem (which are on the path to a base case) may be assumed to workcorrectly. The recursive program needs only to combine solutions to smallerproblems, which are "magically" obtained by recursion, into asolution for the current problem. The mathematical justification for this isproof by induction. This gives the third rule of recursion:

这个证明,或许看起来有点奇怪，因为它几乎跟算法描述一模一样。它说明了在设计一个递归程序的时候，所有相同问题的小小实现(问题就是到元情况的过程)或许假定正确执行了。递归程序仅仅需要将小问题的解决方式组合起来,这些解决方式是通过递归魔法般的组织在一起的，最终成为当前问题的解决方案。这个数学证明过程使用了归纳法。这给出了第三条关于递归的戒律。

[if !supportLists]3.[endif]Design rule.Assume that all the recursive calls work.

3.设计规则,使得所有的递归调用都可以正常工作。

This rule is important because it meansthat when designing recursive programs, you generally don't need to know thedetails of the bookkeeping arrangements, and you don't have to try to tracethrough the myriad of recursive calls. Frequently, it is extremely difficult totrack down the actual sequence of recursive calls. Of course, in many casesthis is an indication of a good use of recursion, since the computer is beingallowed to work out the complicated details. The main problem with recursion isthe hidden bookkeeping costs. Although these costs are almost alwaysjustifiable, because recursive programs not only simplify the algorithm designbut also tend to give cleaner code, recursion should never be used as asubstitute for a simple for loop. We'll discuss the overhead involved inrecursion in more detail in Section 3.3.

这个规则很重要，因为它意味着当你设计一个递归程序的时候，你一般不需要知道栈内细节安排,并且你不必尝试回溯递归调用的路径。通常而言,回溯实际的递归调用顺序非常困难。当然，很多情况下，这是一个递归好的用法的表现，因为计算机被允许计算出这些复杂的磨人的细节。递归的主要问题是栈内存消耗的隐蔽性。虽然那些消耗几乎总是合理的，因为递归程序不仅简化了算法设计，它还能使代码更简洁。递归永远不应该被当做一个简单for循环的替代品。在3.3章节我们将讨论这个递归导致栈内存开销的详细问题。

When writing recursive routines, it iscrucial to keep in mind the four basic rules of recursion:

写递归程序的时候,牢记四条基本递归法则很重要。

[if !supportLists]1. [endif]Base cases.You must always have some base cases, which can be solved without recursion.

1.元情况,你必须总是有几个元情况，可以无需使用递归直接给出答案。

[if !supportLists]2. [endif]Makingprogress. For the cases that are to be solved recursively, the recursive callmust always be to a case that makes progress toward a base case.

2.使进程化，对于那些需要递归解决的情况而言，递归调用必须总是通过一系列进程最终到达元情况。

[if !supportLists]3. [endif]Designrule. Assume that all the recursive calls work.

3.设计规则，使得所有的递归调用都可以工作。

[if !supportLists]4. [endif]Compoundinterest rule. Never duplicate work by solving the same instance of a problemin separate recursive calls.

4.整合有意思的规则。在不同的递归调用不要复制相同的工作通过相同的问题实例

The fourth rule, which will be justified(along with its nickname) in later sections, is the reason that it is generallya bad idea to use recursion to evaluate simple mathematical functions, such asthe Fibonacci numbers. As long as you keep these rules in mind, recursiveprogramming should be straightforward.

将会在后面的章节中被解释(沿用它的名称)的第四条规则，是在通常情况下递归被用来计算简单的数学函数(例如菲波那切数列)是个坏主意的原因。只要你将这些规则牢记于心，递归程序将会非常简单。

Summary

总结

This chapter sets the stage for the rest ofthe book. The time taken by an algorithm confronted with large amounts of inputwill be an important criterion for deciding if it is a good algorithm. (Ofcourse, correctness is most important.)Speed is relative. What is fast for oneproblem on one machine might be slow for another problem or a differentmachine. We will begin to address these issues in the next chapter and will usethe mathematics discussed here to establish a formal model.

这章节是本书其余内容的基础，相对多输入的情况下算法消耗的时间是很重要的评判算法优良的标准。(当然,正确是最重要的!)速度是相对的。对一个机器上的一个问题的快速解决的方案有可能对另一个问题或者不同机器来说就慢了。我们将在下一张开始处理这些问题并且会使用到这张讨论的数学只是去建立一个合适模型。

Exercises

[if !supportLists]1.1   [endif]Writea program to solve the selection problem. Let k = n/2. Draw a table showing therunning time of your program for various values of n.

1.2 Write a program to solve the word puzzle problem.

1.3 Write a procedure to output an arbitrary real number(which might be negative) using only print_digit for I/O.

1.4 C allows statements of the form

#include filename

which reads filename and inserts its contents in place ofthe include statement. Include statements may be nested; in other words, thefile filename may itself contain an include statement, but, obviously, a filecan't include itself in any chain. Write a program that reads in a file andoutputs the file as modified by the include statements.

1.5 Prove the following formulas:

a. log x < x for all x > 0

[if !vml]

[endif]

1.6 Evaluate the following sums:

[if !vml]

[endif]

1.7 Estimate

[if !vml]

[endif]

*1.8 What is[if !vml]

[endif]？

1.9 Let[if !vml]

[endif]be the Fibonacci numbers as definedin Section 1.2. Prove the following:

[if !vml]

[endif]

**c. Give a precise closed-form expression for[if !vml]

[endif]

1.10 Prove the following formulas:

[if !vml]

[endif]

1.1写一个程序解决选择问题。令k=n/2.画一张表，体现你的程序对于不同的n值需要的运行时间。

1.2写一个程序解决单词字谜问题

1.3写一个只用print digit来输出的程序输出一个任意实数(包括负数)

1.4 C语言允许这样形式的语句：

#include filename

它会读取文件名并且插入该文件的内容取代这个#include语句。Include语句可能是嵌入的；换句话说，这个文件名或许它本身就包括一个include语句，但是，很明显，一个文件在任何环节中都不能包括它自己。写一个程序读入一个文件，并且输出被include语句修改后的这个文件。

1.5证明下面的公式：

a. log x < x for all x > 0

[if !vml]

[endif]

1.6计算下列和:

[if !vml]

[endif]

1.7估值：

[if !vml]

[endif]

*1.8[if !vml]

[endif]是什么？

1.9 设[if !vml]

[endif]是1.2节被定义的斐波那契数列。证明下式：

[if !vml]

[endif]

**c. 给出一个精确的封闭式的[if !vml]

[endif]表达式

1.10 证明下列公式：

[if !vml]

[endif]

 

References

There are many good textbooks covering the mathematicsreviewed in this chapter. A small subset is [1], [2], [3], [11], [13], and[14]. Reference [11] is specifically geared toward the analysis of algorithms.It is the first volume of a three-volume series that will be cited throughoutthis text. More advanced material is covered in [6].

有许多好的教材都在这一章复习了数学知识。一小部分是[1], [2], [3], [11], [13],和[14]。参考书[11]是专门面向算法分析的。一个分为三册的一套书的第一册在整书中被引用。更先进的材料在[6]中。

Throughout this book we will assume a knowledge of C [10].Occasionally, we add a feature where necessary for clarity. We also assumefamiliarity with pointers and recursion (the recursion summary in this chapteris meant to be a quick review). We will attempt to provide hints on their usewhere appropriate throughout the textbook. Readers not familiar with theseshould consult [4], [8], [12], or any good intermediate programming textbook.

整本书中，我们都将假设C[10]的知识。偶尔，为了更清晰，我们也有必要加一点特别的知识。我们也假设熟悉指针和递归（本章中递归的总结是一个快速的复习）。我们将会在整本书中要适当的使用它的时候提供提示。不熟悉这个的读者应该去查阅[4]

[8] [12] ，或许任何一本好的作为媒介的编程教材。

General programming style is discussed in several books.Some of the classics are [5], [7], and [9].

比较普遍的编程风格在几本书中都有介绍。[5] [7] [9]都是比较经典的。

[if !supportLists]1.      [endif]M. O.Albertson and J. P. Hutchinson, Discrete Mathematics with Algorithms, JohnWiley & Sons, New York , 1988.

2. Z. Bavel, Math Companion for Computer Science, RestonPublishing Company, Reston, Va., 1982.

3. R. A. Brualdi, Introductory Combinatorics, North-Holland,New York, 1977.

4. W. H. Burge, Recursive Programming Techniques,Addison-Wesley, Reading, Mass., 1975.

5. E. W. Dijkstra, A Discipline of Programming, PrenticeHall, Englewood Cliffs, N.J., 1976.

6. R. L. Graham, D. E. Knuth, and O. Patashnik, ConcreteMathematics, Addison-Wesley, Reading, Mass., 1989.

7. D. Gries, The Science of Programming, Springer-Verlag,New York, 1981.

8. P. Helman and R. Veroff, Walls and Mirrors: IntermediateProblem Solving and Data Structures, 2d ed., Benjamin Cummings Publishing,Menlo Park, Calif., 1988.

9. B. W. Kernighan and P. J. Plauger, The Elements ofProgramming Style, 2d ed., McGraw- Hill, New York, 1978.

10. B. W. Kernighan and D. M. Ritchie, The C ProgrammingLanguage, 2d ed., Prentice Hall, Englewood Cliffs, N.J.,1988.

11. D. E. Knuth, The Art of Computer Programming, Vol. 1:Fundamental Algorithms, 2d ed., Addison-Wesley,Reading, Mass., 1973.

12. E. Roberts, Thinking Recursively, John Wiley & Sons,New York, 1986.

13. F. S. Roberts, Applied Combinatorics, Prentice Hall,Englewood Cliffs, N.J., 1984.

14. A. Tucker, Applied Combinatorics, 2d ed., John Wiley& Sons, New York, 1984.

[if !supportLists]1.      [endif]M. O.

Albertson and J. P. Hutchinson ，离散数学和算法，John Wiley & Sons，纽约，1998

[if !supportLists]2.      [endif]Z.

Bavel，计算机数学，Reston出版公司，Reston,

Va.，1982

[if !supportLists]3.      [endif]R. A.

Brualdi，组合数学介绍，North-Holland,

New York,，1997

[if !supportLists]4.      [endif]Burge,递归编程技术，Addison-Wesley,Reading, Mass., 1975.

[if !supportLists]5.      [endif]W.

Dijkstra,一门编程学科，Prentice Hall, Englewood Cliffs, N.J.,1976.

[if !supportLists]6.      [endif]L.

Graham, D. E. Knuth, and O. Patashnik,具体的数学，Addison-Wesley, Reading,Mass., 1989.

[if !supportLists]7.      [endif]Gries,编程科学，Springer-Verlag,New York, 1981.

[if !supportLists]8.      [endif]Helman

and R. Veroff, Walls and Mirrors:解决问题的中间语言及数据结构，2ded., Benjamin Cummings Publishing, Menlo Park, Calif., 1988.

[if !supportLists]9.      [endif]W.

Kernighan and P. J. Plauger,编程风格的元素，2d ed., McGraw- Hill, NewYork, 1978.