程序设计方法学第七章

第7章 递归程序设计

本章目标

?什么是递归定义，递归的优缺点

?什么是迭代，递归与迭代的区别

？什么是递归数据结构，

有哪些结构是递归数据结构

？什么是简化的函数型递归程序模型，

递归程序的计算规则

？递归程序的正确性证明

内容线索递归的概念递归与迭代程序

递归数据结构 递归程序

递归程序正确性证明

递归：

如果函数体或过程体中出现调用其自身的语句，称为递归。

例如：阶乘函数的定义

当n=0时

当n>0时

递归算法的执行过程

例1：阶乘的递归算法public static long fact(int n) throws Exception{int x;long y;if(n

throw new Exception("参数错！");}if(n == 0) return 1;else{x = n - 1;y = fact(x);return n * y;}

}

递归的表示

一个函数或者数据结构，如果在它们定义的内部有出现定义P ≡ [Si分为Si是基语句，P

直接递归： P包含对自己的引用

间接递归：P包含对另一程序Q的引用，而Q又直接或间接地引用P

递归算法的准确表示为： P ≡ if B then β[Si, P]

其中， B是递归调用受限条件

所以，递归程序依然要考虑终止问题

例题：P192-193

计算阶乘的函数

计算Fibonacci数列

斐波那契数列Fib(n)的递推定义是：

0Fib(n)1

Fib(n1)Fib(n2)当n0时当n1时当n1时64

按照上式，求第n项斐波那契数列的递归函数如下：public static long fib(int n){

if(n == 0 || n == 1) return n; //递归出口

else return fib(n - 1) + fib(n - 2); //递归调用}

递归的优缺点优点：比较直观、精练，逻辑清楚，逼近数学公式的表示编程方便，易读缺点效率较低每一次执行，都必须进行参数替换、环境保护等

大量重复的计算

何时使用递归

在以下三种情况下,常常要用到递归的方法。

1. 定义是递归的

有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。

2. 数据结构是递归的

有些数据结构是递归的。例如,第2章中介绍过的单为什么可以这样递 归定义类型

struct LNode *next;

} LinkList 该定义中，结构体LNode的定义中用到了它自身，即指针域next是一种指向自身类型的指针，所以它是一种递归数据结构。

对于递归数据结构,采用递归的方法编写算法既方便又有效。例如，求一个不带头结点的单链表L的所有data域（假设为int型）之和的递归算法如下：

int Sum(LinkList *L)

{ if (L==NULL)

return 0;

else

return(L->data+Sum(L->next)); }

3. 问题的求解方法是递归的

有些问题的解法是递归的，典型的有Hanoi问题求解，该问题描述是：设有3个分别命名为X,Y和Z的塔座，在塔座X上有n个直径各不相同，从小到大依次编号为1,2,…,n的盘片，现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放。

　　盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X、Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法，并将其转换为非递归算法。

设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上，递归分解的过程是：

Hanoi(n-1,x,z,y)；

Hanoi(n,x,y,z)move(n,x,z):将第n个圆盘从x移到z；

Hanoi(n-1,y,x,z)

x

yz

递归程序的设计

递归的求解的过程均有这样的特征：

　 先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。

而这些子问题具有与原问题相同的求解方法，于是可以再将它们划分成若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。这种自上而下将问题分解、求解,再自上而下引用、合并，求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。

递归算法设计先要给出递归模型，再转换成对应的C/C++语言函数。

　求递归模型的步骤如下：

（1）对原问题f(s)进行分析，假设出合理的“较小问题”f(s‘)（与数学归纳法中假设n=k-1时等式成立相似）；

（2）假设f(s‘)是可解的,在此基础上确定f(s)的解，即给出f(s)与f(s’)之间的关系（与数学归纳法中求证n=k时等式成立的过程相似）；

（3）确定一个特定情况（如f(1)或f(0)）的解,由此作为递归出口（与数学归纳法中求证n=1时等式成立相似）。

由此得到如下递归求解算法： float f(float A[],int i)

{ float m;

if (i==0)

return A[0];

else

{ m=f(A,i-1);

if (m>A[i])

return A[i];

else

return m;

}

}

迭代的概念

迭代(iterate)重复地执行一系列步骤。

迭代法——数值计算中的一种重复方法。

例题：P193~194计算阶乘的函数

计算Fibonacci数列

计算阶乘的函数

public int fact(int n){public int fact(int n){

int result = 1;int result = 1;

for(int i =1; i

result *= i;result *= i;

}}

return result;return result;

}}

递归与迭代程序…

在程序设计中，为了处理重复性的计算，最常采用的方法是组织迭代循环，除此之外，往往还可采用递归计算的方法特别是在非数值领域中更是如此。

除了可调用的其他程序外，还可以直接或间接调用自身的程序称为递归程序。

实质上，递归也是一种循环结构，它把“较复杂”情形的计算归结为“较简单”情形的计算，一直归结到“最简单”情形的计算，并得到计算结果为止。就某种意义而言，递归是一种比迭代循环更强的循环结构。可以证明每个迭代程序原则上总可以转换成与它等价的递归程序，但是，反之不然，即并不是每个递归程序都可以转换成与它等价的迭代程序。

…递归与迭代程序

但就效率而言，递归程序的实现往往比迭代程序耗费更多的时间与存储空间。所以在具体实现时，又希望尽可能把递归程序转化成等价的迭代程序，从而提高程序的时空效率

但是，递归在解决实际问题时是十分有效的Hanoi塔问题

Hilbert图案问题

八皇后问题

骑士游历问题

递归程序的一种模型

下面将讨论一种简化的函数型递归程序模型，其一般形式为

F(x1,x2,….,xn)if p1 then E1 else if p2 then E2

…………

else if pm then Em else Em+1

其中，pi(i=1,2,….m)是测试谓词，Ei(i=1,2,…..m+1)是表达式。

递归程序的一种模型这种函数型递归程序的基本含义是

为了计算自变元为(x1,x2,….xn)的递归函数F(x1,x2…,xn)的值，先测试P1的值，若P1为真，则F的值为E1的值；若P1为假，则接下去测试P2，若P2为真，则F的值为E2的值。按这种方式继续进行测试，直至找到第一个为真的Pi。这时F的值为相应的Ei的值。倘若没有一个Pi(i=1,2,…m)为真，则F的值规定为Em+1的值。

这里所谓的递归，是指F可以在Ei和Pi中出现，这种出现称为F的递归调用。

递归程序的例子…

例 求非负整数x和y的最大公约数GCD(x,y) GCD(x,y) if x=0 then y

else if y

其中，x

可以证明GCD(x,y)确实计算了x和y的最大公约数。例如:

GCD(8,4)= GCD(4,8)= GCD(4,4)

= GCD(4,0)= GCD(0,4)

=4

结构归纳法… 递归程序具有如下结构：

首先指出对于自变元的某些“最简单”的数据如何进行计算

然后指出如何将对于“较复杂”的数据的计算通过递归方法归结为“较简单”的数据的计算

…结构归纳法…

因此，为了证明递归程序的正确性，我们可以采用如下的步骤：

(1) 证明对于“最简单”的数据，程序运行正确；

(2) 假设对于“较简单”的数据，程序运行正确

[归纳假设]，在此基础上证明对于“较复杂”的数据，程序亦运行正确

这里所说的数据，是指自变元所允许取的值。它可以是一般的数值，也可以是由数值、原子或者表等组成的某种数据结构

…结构归纳法

容易看出，这种证明递归程序正确性的基本思想与通常的数学归纳法是很类似的两者的区别：

归纳过程不一定是对简单的变量N进行的，而可以是对程序所操作的数据的结构进行的

通常把这种方法称为结构归纳法。

例子…

例15 证明例1中给出的计算阶乘的递归程序。 F(x)≡if x=1 then 1

else x*F(x-1)

的正确性。

我们要证明对于所有正整数x, F(x)=x!。因而，这个程序的输入、输出断言为

φ(x):x>0(x为整数)

ψ(x,z):z=x!

…例子…

由于这个程序的自变元是整型变量x，所以直接对正整数x进行归纳：

(1) 证明x=1时，F(1)=1=1!

(2) 归纳假设。设对任意正整数x，F(x)=x!。

在此基础上证明，对正整数x+1 ， F(x+1)=(x+1)! 事实上，因为x是正整数，所以x+1=1为假， 于是根据程序有

F(x+1)=(x+1)*F((x+1)-1)=(x+1)*F(x)

=(x+1)*x! (根据归纳假设)

=(x+1)!

F(x)≡if x=1 then 1

else x*F(x-1)

…例子…

这样，我们就证明了对于任何满足输入断言φ(x)的x，程序执行结果将得到z=F(x)=x!，即程序是部分正确的。这个程序的终止性是显然的。

在这个归纳证明中，我们是对程序所操作的数据本身进行归纳。一般说来，只有在相当简单的情形下，才有可能直接对数据本身进行归纳，而在较一般的情形下，必须对程序所操作的数据的结构进行

归纳。

良序归纳法

设(W, )是良序集，P(x)是一个命题，为了证明对于所有的xW, P(x)为真，只要：

1)证明P(x0)为真,（x0是W中的最小元素）

2)归纳假设：假设对于所有的x' x, P(x')为真，在此基础上证明P(x)为真，即可。

偏序集的概念…

设有一个非空集合W和一个定义在W上的二元关系，且这个关系满足下列性质：

(1)传递性，即对于一切a,b,cW,如果a b,b c 则有a c；

(2)反对称性，即对于一切a,bW,如果a b则有；

(3)反自反性，即对于一切a。

称W为具有关系 的偏序集，记为(W, )。

良序集的概念…

设(W, )是一个偏序集，如果不存在由W中的元素构成的无限递减序列a0>a1>a2…，则称(W, )为良序集。

任一偏序集，假如它的每一个非空子集存在最小元素，这种偏序集称为良序集。

…良序集的概念例如：

(1) 若N是自然数的集合，那么(N , )是良序集

而上面的偏序集(A1, ), (B1, )不是良序集。

(2) 若W是非负整数对的集合，在其上定义

字典顺序--

即如果 xi

容易证明，这样规定的(W, )是良序集。

…例子…

例 证明递归程序 GCD(x,y)  if x=0 then y else if y0y>0(x0y0)的

任意整数x和y)。

在证明过程 ，我们将用到GCD函数的下述基本性质： (1) GCD(0，y)=y (2) GCD(x，y)=GCD(y，x) (3) GCD(x，y)=GCD(x，y-x)(当y>x时)

…例子…

考察这个程序，我们发现第一个递归调用GCD的地方(即GCD(y,x)),其第一个自变元(即y)比调用前(即x)简单(指y

这就启示所选取良序集(W, )为 W={(x,y)x>0y>0(x0y0)为字典顺序。

…例子…

为证明GCD(x,y)正确地计算x和y的最大公约数，则需要：

(1) 证明对于W中的最小元素(0，1)，程序能正确地运行。

事实上，这时有GCD(0,1)=1，这显然是正确的。•

(2) 归纳假设：假设对于一切(x’,y’)

事实上，可就以下3种情形分别论证。

•

…例子…

①x=0,这时GCD(x,y)=GCD(0,y)=y程序运行正确。这是因为由GCD函数的性质(1)可知，程序运行正确。②x0y

由于x0y>x，故(y,x)

③ x≠0  y>=x，这时GCD(x,y)=GCD(x,y-x)，程序运行正确。这是因为：

由于x≠0  y >= x，故y-x

(x,y-x)

实验

8皇后问题：在8*8棋盘内放置8个皇后，要求同一行、同一列，对角线最多只能有一个皇后。要求用递归方法编写。

5 - 42

第7章 递归程序设计

本章目标

?什么是递归定义，递归的优缺点

?什么是迭代，递归与迭代的区别

？什么是递归数据结构，

有哪些结构是递归数据结构

？什么是简化的函数型递归程序模型，

递归程序的计算规则

？递归程序的正确性证明

内容线索递归的概念递归与迭代程序

递归数据结构 递归程序

递归程序正确性证明

递归：

如果函数体或过程体中出现调用其自身的语句，称为递归。

例如：阶乘函数的定义

当n=0时

当n>0时

递归算法的执行过程

例1：阶乘的递归算法public static long fact(int n) throws Exception{int x;long y;if(n

throw new Exception("参数错！");}if(n == 0) return 1;else{x = n - 1;y = fact(x);return n * y;}

}

递归的表示

一个函数或者数据结构，如果在它们定义的内部有出现定义P ≡ [Si分为Si是基语句，P

直接递归： P包含对自己的引用

间接递归：P包含对另一程序Q的引用，而Q又直接或间接地引用P

递归算法的准确表示为： P ≡ if B then β[Si, P]

其中， B是递归调用受限条件

所以，递归程序依然要考虑终止问题

例题：P192-193

计算阶乘的函数

计算Fibonacci数列

斐波那契数列Fib(n)的递推定义是：

0Fib(n)1

Fib(n1)Fib(n2)当n0时当n1时当n1时64

按照上式，求第n项斐波那契数列的递归函数如下：public static long fib(int n){

if(n == 0 || n == 1) return n; //递归出口

else return fib(n - 1) + fib(n - 2); //递归调用}

递归的优缺点优点：比较直观、精练，逻辑清楚，逼近数学公式的表示编程方便，易读缺点效率较低每一次执行，都必须进行参数替换、环境保护等

大量重复的计算

何时使用递归

在以下三种情况下,常常要用到递归的方法。

1. 定义是递归的

有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。

2. 数据结构是递归的

有些数据结构是递归的。例如,第2章中介绍过的单为什么可以这样递 归定义类型

struct LNode *next;

} LinkList 该定义中，结构体LNode的定义中用到了它自身，即指针域next是一种指向自身类型的指针，所以它是一种递归数据结构。

对于递归数据结构,采用递归的方法编写算法既方便又有效。例如，求一个不带头结点的单链表L的所有data域（假设为int型）之和的递归算法如下：

int Sum(LinkList *L)

{ if (L==NULL)

return 0;

else

return(L->data+Sum(L->next)); }

3. 问题的求解方法是递归的

有些问题的解法是递归的，典型的有Hanoi问题求解，该问题描述是：设有3个分别命名为X,Y和Z的塔座，在塔座X上有n个直径各不相同，从小到大依次编号为1,2,…,n的盘片，现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放。

　　盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X、Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法，并将其转换为非递归算法。

设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上，递归分解的过程是：

Hanoi(n-1,x,z,y)；

Hanoi(n,x,y,z)move(n,x,z):将第n个圆盘从x移到z；

Hanoi(n-1,y,x,z)

x

yz

递归程序的设计

递归的求解的过程均有这样的特征：

　 先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。

而这些子问题具有与原问题相同的求解方法，于是可以再将它们划分成若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。这种自上而下将问题分解、求解,再自上而下引用、合并，求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。

递归算法设计先要给出递归模型，再转换成对应的C/C++语言函数。

　求递归模型的步骤如下：

（1）对原问题f(s)进行分析，假设出合理的“较小问题”f(s‘)（与数学归纳法中假设n=k-1时等式成立相似）；

（2）假设f(s‘)是可解的,在此基础上确定f(s)的解，即给出f(s)与f(s’)之间的关系（与数学归纳法中求证n=k时等式成立的过程相似）；

（3）确定一个特定情况（如f(1)或f(0)）的解,由此作为递归出口（与数学归纳法中求证n=1时等式成立相似）。

由此得到如下递归求解算法： float f(float A[],int i)

{ float m;

if (i==0)

return A[0];

else

{ m=f(A,i-1);

if (m>A[i])

return A[i];

else

return m;

}

}

迭代的概念

迭代(iterate)重复地执行一系列步骤。

迭代法——数值计算中的一种重复方法。

例题：P193~194计算阶乘的函数

计算Fibonacci数列

计算阶乘的函数

public int fact(int n){public int fact(int n){

int result = 1;int result = 1;

for(int i =1; i

result *= i;result *= i;

}}

return result;return result;

}}

递归与迭代程序…

在程序设计中，为了处理重复性的计算，最常采用的方法是组织迭代循环，除此之外，往往还可采用递归计算的方法特别是在非数值领域中更是如此。

除了可调用的其他程序外，还可以直接或间接调用自身的程序称为递归程序。

实质上，递归也是一种循环结构，它把“较复杂”情形的计算归结为“较简单”情形的计算，一直归结到“最简单”情形的计算，并得到计算结果为止。就某种意义而言，递归是一种比迭代循环更强的循环结构。可以证明每个迭代程序原则上总可以转换成与它等价的递归程序，但是，反之不然，即并不是每个递归程序都可以转换成与它等价的迭代程序。

…递归与迭代程序

但就效率而言，递归程序的实现往往比迭代程序耗费更多的时间与存储空间。所以在具体实现时，又希望尽可能把递归程序转化成等价的迭代程序，从而提高程序的时空效率

但是，递归在解决实际问题时是十分有效的Hanoi塔问题

Hilbert图案问题

八皇后问题

骑士游历问题

递归程序的一种模型

下面将讨论一种简化的函数型递归程序模型，其一般形式为

F(x1,x2,….,xn)if p1 then E1 else if p2 then E2

…………

else if pm then Em else Em+1

其中，pi(i=1,2,….m)是测试谓词，Ei(i=1,2,…..m+1)是表达式。

递归程序的一种模型这种函数型递归程序的基本含义是

为了计算自变元为(x1,x2,….xn)的递归函数F(x1,x2…,xn)的值，先测试P1的值，若P1为真，则F的值为E1的值；若P1为假，则接下去测试P2，若P2为真，则F的值为E2的值。按这种方式继续进行测试，直至找到第一个为真的Pi。这时F的值为相应的Ei的值。倘若没有一个Pi(i=1,2,…m)为真，则F的值规定为Em+1的值。

这里所谓的递归，是指F可以在Ei和Pi中出现，这种出现称为F的递归调用。

递归程序的例子…

例 求非负整数x和y的最大公约数GCD(x,y) GCD(x,y) if x=0 then y

else if y

其中，x

可以证明GCD(x,y)确实计算了x和y的最大公约数。例如:

GCD(8,4)= GCD(4,8)= GCD(4,4)

= GCD(4,0)= GCD(0,4)

=4

结构归纳法… 递归程序具有如下结构：

首先指出对于自变元的某些“最简单”的数据如何进行计算

然后指出如何将对于“较复杂”的数据的计算通过递归方法归结为“较简单”的数据的计算

…结构归纳法…

因此，为了证明递归程序的正确性，我们可以采用如下的步骤：

(1) 证明对于“最简单”的数据，程序运行正确；

(2) 假设对于“较简单”的数据，程序运行正确

[归纳假设]，在此基础上证明对于“较复杂”的数据，程序亦运行正确

这里所说的数据，是指自变元所允许取的值。它可以是一般的数值，也可以是由数值、原子或者表等组成的某种数据结构

…结构归纳法

容易看出，这种证明递归程序正确性的基本思想与通常的数学归纳法是很类似的两者的区别：

归纳过程不一定是对简单的变量N进行的，而可以是对程序所操作的数据的结构进行的

通常把这种方法称为结构归纳法。

例子…

例15 证明例1中给出的计算阶乘的递归程序。 F(x)≡if x=1 then 1

else x*F(x-1)

的正确性。

我们要证明对于所有正整数x, F(x)=x!。因而，这个程序的输入、输出断言为

φ(x):x>0(x为整数)

ψ(x,z):z=x!

…例子…

由于这个程序的自变元是整型变量x，所以直接对正整数x进行归纳：

(1) 证明x=1时，F(1)=1=1!

(2) 归纳假设。设对任意正整数x，F(x)=x!。

在此基础上证明，对正整数x+1 ， F(x+1)=(x+1)! 事实上，因为x是正整数，所以x+1=1为假， 于是根据程序有

F(x+1)=(x+1)*F((x+1)-1)=(x+1)*F(x)

=(x+1)*x! (根据归纳假设)

=(x+1)!

F(x)≡if x=1 then 1

else x*F(x-1)

…例子…

这样，我们就证明了对于任何满足输入断言φ(x)的x，程序执行结果将得到z=F(x)=x!，即程序是部分正确的。这个程序的终止性是显然的。

在这个归纳证明中，我们是对程序所操作的数据本身进行归纳。一般说来，只有在相当简单的情形下，才有可能直接对数据本身进行归纳，而在较一般的情形下，必须对程序所操作的数据的结构进行

归纳。

良序归纳法

设(W, )是良序集，P(x)是一个命题，为了证明对于所有的xW, P(x)为真，只要：

1)证明P(x0)为真,（x0是W中的最小元素）

2)归纳假设：假设对于所有的x' x, P(x')为真，在此基础上证明P(x)为真，即可。

偏序集的概念…

设有一个非空集合W和一个定义在W上的二元关系，且这个关系满足下列性质：

(1)传递性，即对于一切a,b,cW,如果a b,b c 则有a c；

(2)反对称性，即对于一切a,bW,如果a b则有；

(3)反自反性，即对于一切a。

称W为具有关系 的偏序集，记为(W, )。

良序集的概念…

设(W, )是一个偏序集，如果不存在由W中的元素构成的无限递减序列a0>a1>a2…，则称(W, )为良序集。

任一偏序集，假如它的每一个非空子集存在最小元素，这种偏序集称为良序集。

…良序集的概念例如：

(1) 若N是自然数的集合，那么(N , )是良序集

而上面的偏序集(A1, ), (B1, )不是良序集。

(2) 若W是非负整数对的集合，在其上定义

字典顺序--

即如果 xi

容易证明，这样规定的(W, )是良序集。

…例子…

例 证明递归程序 GCD(x,y)  if x=0 then y else if y0y>0(x0y0)的

任意整数x和y)。

在证明过程 ，我们将用到GCD函数的下述基本性质： (1) GCD(0，y)=y (2) GCD(x，y)=GCD(y，x) (3) GCD(x，y)=GCD(x，y-x)(当y>x时)

…例子…

考察这个程序，我们发现第一个递归调用GCD的地方(即GCD(y,x)),其第一个自变元(即y)比调用前(即x)简单(指y

这就启示所选取良序集(W, )为 W={(x,y)x>0y>0(x0y0)为字典顺序。

…例子…

为证明GCD(x,y)正确地计算x和y的最大公约数，则需要：

(1) 证明对于W中的最小元素(0，1)，程序能正确地运行。

事实上，这时有GCD(0,1)=1，这显然是正确的。•

(2) 归纳假设：假设对于一切(x’,y’)

事实上，可就以下3种情形分别论证。

•

…例子…

①x=0,这时GCD(x,y)=GCD(0,y)=y程序运行正确。这是因为由GCD函数的性质(1)可知，程序运行正确。②x0y

由于x0y>x，故(y,x)

③ x≠0  y>=x，这时GCD(x,y)=GCD(x,y-x)，程序运行正确。这是因为：

由于x≠0  y >= x，故y-x

(x,y-x)

实验

8皇后问题：在8*8棋盘内放置8个皇后，要求同一行、同一列，对角线最多只能有一个皇后。要求用递归方法编写。

5 - 42