chapter 7 recursion(递归) and linked data structures(链接数据结构)

妖狐艹你老母 2022-08-23 15:52 149阅读 0赞

一、recursion(递归)

**1、recursion(递归) 概念**：程序调用自身的编程技巧称为递归（ recursion）。

在过程或函数的定义或说明中直接或间接地出现调用自身的一种方法，则称这样的程序嵌套定  
义为递归定义。  
递归算法是把处理问题的方法定义成与原问题处理方法相同的过程，在处理问题的过程中又调用自身  
定义的函数或过程。

例如，在数学上，所有偶数的集合可递归地定义为：  
①0是一个偶数；  
②一个偶数和2的和是一个偶数。  
可见，仅需两句话就能定义一个由无穷多个元素组成的集合。在程序中，递归是通过函数或过程的  
调用来实现的。函数或过程直接调用其自身，称为直接递归；函数(function)或过程(procedure)间接调用其自身，称为间接递归。

注意：函数(function)和过程(procedure)之间的区别：

过程是编制程序时定义的一个语句序列，用来完成某种指定的操作。过程说明是由过程首和分程序（说明部分和过程体）组成，过程定义如下：  
过程定义：  
procedure 过程标识符 形式参数表;分程序;  
过程调用：  
过程标识符(实际参数表);(\*若没有参数,则一对圆括号间的内容(包括括号本身)可不要\*)  
例:  
program proconcept(output);  
type st=string\[12\];  
var s:st;  
procedure p(s1:st);  
begin  
write(s1);  
end;  
begin  
s:='welcome you!';  
p(s);  
end.

函数是子程序的另一种形式,也是编制程序时定义的一个语句序列.与过程不同的是函数不以实现某种操作为目的,而仅是为了获得一个计算结果值.这个结果值最终是通过函数名返回给调用者的,因此函数名具有值的类型.PASCAL语言规定一个函数只能求出一个简单值,所以确切地说函数名的类型只能是简单类型.函数的说明也是由函数首部和分程序(说明部分和函数体)组成,其定义语法如下:  
函数定义:  
function 函数标识符 形式参数表:函数类型标识符;分程序;  
函数调用:  
与标准函数的使用方法一样,例:  
program fucconcept(output);  
var x:integer;  
function f(m:integer):integer;  
begin  
f:=sqr(m)  
end;  
begin  
x:=f(5);  
writeln('x=',x)  
end.

**2、递归程序的执行过程及程序设计:**

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。  
（1）递归程序的执行过程  
递归程序在执行过程中，一般具有如下模式：  
①将调用程序的返回地址、相应的调用前变量保存在栈中；  
②执行被调用的程序或函数；  
③若满足退出递归的条件，则退出递归，并从栈顶上弹回返回地址、返回变量的值，继续沿着返回地址，  
向下执行程序；  
④否则继续递归调用，只是递归调用的参数发生变化：增加一个量或减少一个量，重复执行直到递归调  
用结束。

（2）递归程序设计  
能够用递归算法解决的问题，一般满足如下要求：  
①需要求解的问题可以化为子问题求解，其子问题的求解方法与原问题相同，只是数量的增加或减少；  
②递归调用的次数是有限的；必须有递归结束的条件，称为递归出口。

**3、递归算法的简单应用:**

\[例1\] 植树节那天，有五位参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少  
棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；…  
如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10 棵。到底第一位同学植了  
多少棵树？  
分析：设第一位同学植树的棵数为a1，欲求a1，需从第五位同学植树的棵数a5入手，根据“多两棵”  
这个规律，按照一定顺序逐步进行推算：  
①a5=10;  
②a4=a5+2=12;  
③a3=a4+2=14;  
④a2=a3+2=16;  
⑤a1=a2+2=18;

Pascal程序：  
Program Exam1;  
Var i, a: byte;  
begin  
a:=10; \{以第五位同学的棵数为递推的起始值\}  
for i :=1 to 4 do \{还有4人，递推计算4次\}  
a:= a+2; \{递推运算规律\}  
writeln(’The Num is’, a);  
readln  
end.  
  
  
递推算法以初始\{起点\}值为基础，用相同的运算规律，逐次重复运算，直至运算结束。这种从“起点”  
重复相同的方法直至到达一定“边界”，犹如单向运动，用循环可以实现。递推的本质是按规律逐次推出  
（计算）下一步的结果。

\[例2\]阶乘。

最简单的可以归为递归问题的就是阶乘，1的阶乘我们知道是1，2的阶乘为2\*1=2\*1!，而3的阶乘又是3\*2!...这样我们就能够知道如何用递归去实现n的阶乘了。递归的实质：将复杂问题递归为简单问题解决

1.  **public** **class** Factorial \{
2.  **public** **static** **int** factorial (**int** n)\{
3.  **int** result = 0;
4.  
5.  **if** (n <= 1)\{
6.  result = 1;
7.  \}
8.  **else** **if** (n > 1)\{
9.  result = n \* factorial (n-1);
10. \}
11. **return** result;
12. \}
13. 
14. **public** **static** **void** main (String args\[\])\{
15. **for** (**int** i=0; i<10; i++)
16. System.out.print(factorial (i) +" ");
17. \}
18. \}

\[例3 \] the towers of Hanoi (汉诺塔问题)

我们再来看看稍微复杂点的，也比较有意思，汉诺塔问题：有1，2，3这3个柱子，1号柱子上有n个盘子（盘子由小到大地串在上面，且小盘子永远不能在大盘子下面），以2号柱子为临时存放地，最终将n个盘子移到3号柱子上。将这个问题分析为递归问题，分解出以下三点：

1. 从1号柱子移动n-1个盘子到2号柱子，3号柱子为临时存放点；

2. 从1号柱子将第n个盘子移到3号柱子；

3. 将n-1个柱子从2号柱子移到3号柱子，1号柱子为临时存放点。

Hanoi塔问题  
一块板上有三根针，A，B，C。A针上套有多个个大小不等的圆盘，大的在下，小的在上。要把这64个圆盘从A针移动C针上，每次只能移动一个圆盘，移动可以借助B针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。求移动的步骤。  
本题算法分析如下，设A上有n个盘子。  
如果n=1，则将圆盘从A直接移动到C。  
如果n=2，则：  
1.将A上的n-1(等于1)个圆盘移到B上；  
2.再将A上的一个圆盘移到C上；  
3.最后将B上的n-1(等于1)个圆盘移到C上。  
如果n=3，则：  
A. 将A上的n-1(等于2，令其为n\`)个圆盘移到B(借助于C)，步骤如下：  
(1)将A上的n\`-1(等于1)个圆盘移到C上。  
(2)将A上的一个圆盘移到B。  
(3)将C上的n\`-1(等于1)个圆盘移到B。  
B. 将A上的一个圆盘移到C。  
C. 将B上的n-1(等于2，令其为n\`)个圆盘移到C(借助A)，步骤如下：  
(1)将B上的n\`-1(等于1)个圆盘移到A。  
(2)将B上的一个盘子移到C。  
(3)将A上的n\`-1(等于1)个圆盘移到C。  
到此，完成了三个圆盘的移动过程。  
从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：  
第一步 把A上的n-1个圆盘移到B上；  
第二步 把A上的一个圆盘移到C上；  
第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。  
当n=3时，第一步和第三步又分解为类同的三步，即把n\`-1个圆盘从一个针移到另一个针上，这里的n\`=n-1。 显然这是一个**递归**过程，程序解答如下：

1.  **public** **class** Hanoi \{
2.  **public** **static** **void** hanoi (**int** movingPans, String sourcePillar, String targetPillar, String tempPillar)\{
3.  **if** (movingPans == 1)\{
4.  movePans (1, sourcePillar, targetPillar);
5.  \}
6.  **else**\{
7.  hanoi(movingPans-1, sourcePillar, tempPillar, targetPillar);
8.  movePans (movingPans, sourcePillar, targetPillar);
9.  hanoi(movingPans-1, tempPillar, targetPillar, sourcePillar);
10. \}
11. \}
12. 
13. **public** **static** **void** movePans (**int** panNum, String sourcePillar, String targetPillar)\{
14. System.out.println("Move "\+ panNum +" form "\+ sourcePillar +"\# to "\+ targetPillar +"\#");
15. \}
16. 
17. **public** **static** **void** main(String args\[\])\{
18. System.out.println("3个盘子的汉诺塔问题：");
19. hanoi(3, "1", "3", "2");
20. System.out.println("5个盘子的汉诺塔问题：");
21. hanoi(5, "1", "3", "2");
22. \}
23. \}

1.  3个盘子的汉诺塔问题：
2.  Move 1 form 1\# to 3\#
3.  Move 2 form 1\# to 2\#
4.  Move 1 form 3\# to 2\#
5.  Move 3 form 1\# to 3\#
6.  Move 1 form 2\# to 1\#
7.  Move 2 form 2\# to 3\#
8.  Move 1 form 1\# to 3\#
9.  5个盘子的汉诺塔问题：
10. Move 1 form 1\# to 3\#
11. Move 2 form 1\# to 2\#
12. Move 1 form 3\# to 2\#
13. Move 3 form 1\# to 3\#
14. Move 1 form 2\# to 1\#
15. Move 2 form 2\# to 3\#
16. Move 1 form 1\# to 3\#
17. Move 4 form 1\# to 2\#
18. Move 1 form 3\# to 2\#
19. Move 2 form 3\# to 1\#
20. Move 1 form 2\# to 1\#
21. Move 3 form 3\# to 2\#
22. Move 1 form 1\# to 3\#
23. Move 2 form 1\# to 2\#
24. Move 1 form 3\# to 2\#
25. Move 5 form 1\# to 3\#
26. Move 1 form 2\# to 1\#
27. Move 2 form 2\# to 3\#
28. Move 1 form 1\# to 3\#
29. Move 3 form 2\# to 1\#
30. Move 1 form 3\# to 2\#
31. Move 2 form 3\# to 1\#
32. Move 1 form 2\# to 1\#
33. Move 4 form 2\# to 3\#
34. Move 1 form 1\# to 3\#
35. Move 2 form 1\# to 2\#
36. Move 1 form 3\# to 2\#
37. Move 3 form 1\# to 3\#
38. Move 1 form 2\# to 1\#
39. Move 2 form 2\# to 3\#
40. Move 1 form 1\# to 3\#

\[例4 \] 快速排序(quick sort)

快速排序是目前使用可能最广泛的排序算法了。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

对于输入的序列，如足够小，就直接进行排序；否则分三步走：

1.  分解：将序列一分为二（两子序列非空），使前一子序列之元素皆不大于后一子序列的任一元素；
2.  递归求解：递归调用，再分别对上一步骤得到的子序列进行排序；
3.  合并：在对上一步骤之两子序列都排好序后，整个序列的排序即完成。

快速排序的核心在于分割算法，也可以说是最有技巧的部分。

假设要排序的数组是A\[1\]……A\[N\]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A\[1\]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

A\[1\] A\[2\] A\[3\] A\[4\] A\[5\] A\[6\] A\[7\]：

49 38 65 97 76 13 27

进行第一次交换后： 27 38 65 97 76 13 49

( 按照算法的第三步从后面开始找

进行第二次交换后： 27 38 49 97 76 13 65

( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )

进行第三次交换后： 27 38 13 97 76 49 65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后： 27 38 13 49 76 97 65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态 \{49 38 65 97 76 13 27\}

进行一次快速排序之后划分为 \{27 38 13\} 49 \{76 97 65\}

分别对前后两部分进行快速排序 \{13\} 27 \{38\}

结束 结束 \{49 65\} 76 \{97\}

49 \{65\} 结束

结束

图6 快速排序全过程

1）、设有N（假设N=10）个数，存放在S数组中；

2）、在S\[1。。N\]中任取一个元素作为比较基准，例如取T=S\[1\]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S\[1。。K-1\]<=S\[K\]<=S\[K+1..N\]，即在S\[K\]以前的数都小于S\[K\]，在S\[K\]以后的数都大于S\[K\]；

3）、利用分治思想（即大化小的策略）可进一步对S\[1。。K-1\]和S\[K+1。。N\]两组数据再进行快速排序直到分组对象只有一个数据为止。

如具体数据如下，那么第一躺快速排序的过程是：

数组下标： 1 2 3 4 5 6 7 8 9 10

45 36 18 53 72 30 48 93 15 36

I J

（1） 36 36 18 53 72 30 48 93 15 45

（2） 36 36 18 45 72 30 48 93 15 53

（3） 36 36 18 15 72 30 48 93 45 53

（4） 36 36 18 15 45 30 48 93 72 53

（5） 36 36 18 15 30 45 48 93 72 53

通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S\[1。。5\]和S\[6。。10\]分别进行快速排序。程序代码如下：

import java.io.\*;  
import java.util.\*;

class QuickSort  
\{  
int head,tail,akey;  
//在数组的部分区间\[start...end\]之间进行快速排序的递归算法  
public void quickSort(int\[\] array,int start,int end)\{  
if(start<end)\{  
head=start;  
tail=end;  
akey=array\[start\];  
do\{  
System.out.println("akey");  
System.out.println(akey);  
while(array\[tail\]>=akey&&tail>head)  
\{tail--; //从尾向前查找  
System.out.println(tail);\}  
if(head<tail)  
array\[head++\]=array\[tail\]; //将表尾较小的元素移到前端  
while(array\[head\]<=akey&&tail>head)  
head++; //从前向后查找  
if(head<tail)  
array\[tail--\]=array\[head\]; //将前面较大的元素移到尾端  
\}while(head<tail);  
array\[head\]=akey; //将基准放到正确的位置上  
for(int j=0;j<array.length;j++)\{  
System.out.println(array\[j\]);  
\}  
quickSort(array,start,tail-1); //对前半部分子区间进行递归排序  
quickSort(array,tail+1,end); //对后半部分子区间进行递归排序

public class Hanoi \{  
public static void main(String\[\] args) \{  
int\[\] ii=\{10,100,32\};  
System.out.println("未排序：");  
for(int j=0;j<ii.length;j++)\{  
System.out.println(ii\[j\]);  
\}  
QuickSort a=new QuickSort();  
a.quickSort(ii,0,ii.length-1);  
System.out.println("排序之后：");  
for(int j=0;j<ii.length;j++)\{  
System.out.println(ii\[j\]);  
\}