计算机的威力源自其反复执行同一任务或同一任务不同版本的能力。在计算领域，迭代这一主题会以多种形式出现。数据模型中的很多概念（比如表）都是某种形式的重复，比如“表要么为空，要么由一个元素接一个元素，再接一个元素，如此往复而成”。使用迭代，程序和算法可以在不需要单独指定大量相似步骤的情况下，执行重复性的任务，如“执行下一步骤1000次”。编程语言使用像C语言中的while语句和for语句那样的循环结构，来实现迭代算法。

与重复密切相关的是递归，在递归技术中，概念是直接或间接由其自身定义的。例如，我们可以通过“表要么为空，要么是一个元素后面再跟上一个表”这样的描述来定义表。很多编程语言都支持递归。在C语言中，函数F是可以调用自身的，既可以从F的函数体中直接调用自己，也可以通过一连串的函数调用，最终间接调用F。另一个重要思想——归纳，是与“递归”密切相关的，而且常用于数学证明中。

迭代、归纳和递归都是基本概念，会以多种形式出现在数据模型、数据结构和算法中。下面介绍了一些使用这些概念的例子，每项内容都会在本书中详细介绍。

1. 迭代技术。反复执行一系列操作的最简单方法就是使用迭代结构，比如C语言中的for语句。

2. 递归程序设计。C语言及其他众多语言都允许函数递归，即函数可以直接或间接地调用自己。对新手程序员来说，编写迭代程序通常比写递归程序更安全，不过本书的一个重要目标就是让读者习惯在适当的时候用递归的方式来思考和编程。递归程序更易于编写、分析和理解。

符号：求和符号和求积符号

加大字号的大写希腊字母∑通常用来表示求和，如。这个特殊的表达式表示从1到n 这n个整数的和，也就是1+2+3+ … +n。更加一般化的情况是，我们可以对任何具有求和指标（summation index）i 的函数f (i )求和。（当然，这个指标也可能是i 以外的一些符号。）表达式就表示

f (a) + f (a + 1) + f (a + 2) + … + f (b)

例如，就表示4 + 9 + 16 + … + m2 的和，这里的函数f 就是“求平方”，而我们用了指标j 来代替i。

作为特例，如果b< a，那么表达式不含任何项，当然，其值也就是0了。如果b=a，那么表达式只有i=a 时的那一项。因此，的值就是f (a)。

用于求积的类似符号是个大号的大写希腊字母 Π。表达式就表示

f (a) × f (a + 1) × f (a + 2) × … × f (b)

的积，如果b<a，那么该表达式的值为1。

3. 归纳证明。“归纳证明”是用来表明命题为真的一项重要技术。从2.3节开始，我们将广泛介绍归纳证明。下面是归纳证明最简单的一种形式。我们有与变量n相关的命题S(n)，希望证明S(n)为真。要证明S(n)，首先要提供依据，也就是n为某个值时的命题S(n)。例如，我们可以令n=0，并证明命题S(0)。接着，我们必须对归纳步骤加以证明，我们要证明，对应参数某个值的命题S，是由对应参数前一个值的相同命题S得出的，也就是说，对所有的n≥0，可从S(n)得到S(n+1)。例如，S(n)可能是常见的求和公式

　　　　　　(2.1)

这是说1到n这n个整数的和等于n(n+1)/2。特例可以是S(1)，即等式(2.1)在n为1时的情况，也就是1=1×2/2。归纳步骤就是要表明，由可以得出，前者就是S(n)，是等式(2.1)本身，而后者则是S(n+1)，就是用n+1替换了等式(2.1)中的n。2.3节将会为大家展示如何进行这样的证明。

4. 程序正确性证明。在计算机科学中，我们常希望能够证明与程序有关的命题S(n)为真，不管是采用正式的还是非正式的方式。例如，命题S(n)可能描述了某个循环的第n次迭代中什么为真，或是对某个函数的第n次递归调用来说什么为真。对这类命题的证明一般都使用归纳证明。

5. 归纳定义。计算机科学的很多重要概念，特别是那些涉及数据模型的，最好用归纳的形式来定义，也就是我们给出定义该概念最简单形式的基本规则，以及可用来从该概念较小实例构建更大实例的归纳规则。举例来说，我们提到过的表就可由基本规则（空表是表）加上归纳规则（一个元素后面跟上一个表也是表）来定义。

6. 运行时间的分析。算法处理不同大小的输入所花的时长（算法的“运行时间”）是衡量其“优良性”的一项重要指标。当算法涉及递归时，我们会使用名为递推方程的公式，它是种归纳定义，可以预测算法处理不同大小的输入所花的时间。