第5章

递归
C H A P T E R5




在算法设计中经常需要用递归方法求解，特别是在后面的树和二叉树、图、查找及排序等章节中会大量地遇到递归算法。递归是计算机科学中的一个重要的工具，很多程序设计语言（例如Java）都支持递归程序设计。本章介绍递归的定义和递归算法设计的方法等，为后面的学习打下基础。
主要学习要点如下： 
(1) 递归的定义和递归模型。
(2) 递归算法设计的一般方法。
(3) 灵活运用递归算法解决一些较复杂的应用问题。


视频讲解


5.1什么是递归
5.1.1递归的定义

在定义一个过程或函数时有时会出现调用本过程或本函数的成分，称之为递归。若调用自身，称之为直接递归。若过程或函数A（）调用过程或函数B（），而B（）又调用A（），称之为间接递归。在算法设计中，任何间接递归算法都可以转换为直接递归算法来实现，所以后面主要讨论直接递归。
递归不仅是数学中的一个重要概念，也是计算技术中重要的概念之一。在计算技术中，与递归有关的概念有递归数列、递归过程、递归算法、递归程序和递归方法等。
如果一个递归过程或递归函数中的递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。
【例5.1】以下是求n!(n为正整数)的递归函数，它属于什么类型的递归？

int fun(int n)

{if(n==1)//语句1

return(1);//语句2


else//语句3

return(fun(n-1)*n);//语句4

}

解： 在函数fun(n)求解过程中调用fun(n-1)(语句4)，它是一个直接递归函数。由于递归调用是最后一条语句，所以它又属于尾递归。
递归算法通常把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程中所需要的多次重复计算，大大减少了算法的代码量。
一般来说，能够用递归解决的问题应该满足以下3个条件： 
(1) 需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。
(2) 递归调用的次数必须是有限的。
(3) 必须有结束递归的条件来终止递归。
递归算法的优点是结构简单、清晰，易于阅读，方便其正确性的证明； 缺点是算法执行中占用的内存空间较多，执行效率低，不容易优化。


视频讲解




5.1.2何时使用递归
在以下3种情况下经常要用到递归方法。
1. 定义是递归的
有许多数学公式、数列等的定义是递归的，例如求n!和Fibonacci(斐波那契)数列等。对于这些问题的求解，可以将其递归定义直接转化为对应的递归算法，例如求n!可以转化为例5.1的递归算法。求Fibonacci数列的递归算法如下： 

int Fib(int n) //求Fibonacci数列的第n项

{if(n==1 || n==2)

return 1;

else

return Fib(n-1)+Fib(n-2);

}

2. 数据结构是递归的
有些数据结构是递归的，例如第2章中介绍过的单链表就是一种递归数据结构，其结点类定义如下： 

class LinkNode<E>//单链表结点泛型类

{E data;

LinkNode<E> next;//下一个结点的指针

public LinkNode()//构造方法

{next=null;}

public LinkNode(E d)//重载构造方法

{data=d;

next=null;

}

}

其中，指针成员next是一种指向自身类型结点的指针，所以它是一种递归数据结构。
对于递归数据结构，采用递归的方法编写算法既方便又有效。例如，求一个不带头结点的单链表p中的所有data成员(假设为int型)之和的递归算法如下： 

public static int Sum(LinkNode<Integer> p)

{if(p==null) return 0;

else return(p.data+Sum(p.next));

}

说明： 对于第2章讨论的单链表对象L，L.head为头结点，将L.head.next看成不带头结点的单链表。
3. 问题的求解方法是递归的
有些问题的解法是递归的，典型的有Hanoi（汉诺）塔问题的求解，该问题是设有3个分别命名为X、Y和Z的塔座，在塔座X上有n个直径各不相同的盘片，从小到大依次编号为1、2、……、n，现要求将X塔座上的n个盘片移到塔座Z上并按同样的顺序叠放，在移动盘片时必须遵守以下规则： 每次只能移动一个盘片； 盘片可以插在X、Y和Z中的任一塔座上； 任何时候都不能将一个较大的盘片放在较小的盘片上。图5.1所示为n=4的Hanoi问题，设计求解该问题的算法。



图5.1Hanoi塔问题(n=4)


Hanoi塔问题特别适合采用递归方法来求解。设Hanoi(n，X，Y，Z)表示将n个盘片从X塔座借助Y塔座移动到Z塔座上，递归分解的过程是： 





其含义是首先将X塔座上的n-1个盘片借助Z塔座移动到Y塔座上，此时X塔座上只有一个盘片，将其直接移动到Z塔座上，再将Y塔座上的n-1个盘片借助X塔座移动到Z塔座上。由此得到Hanoi递归算法如下： 

public static void Hanoi(int n,char X,char Y,char Z)

{if(n==1)//只有一个盘片的情况

System.out.printf("将第%d个盘片从%c移动到%c＼n",n,X,Z);

else//有两个或多个盘片的情况

{Hanoi(n-1,X,Z,Y);

System.out.printf("将第%d个盘片从%c移动到%c＼n",n,X,Z);

Hanoi(n-1,Y,X,Z);

}

}




视频讲解


5.1.3递归模型
递归模型是递归算法的抽象，它反映一个递归问题的递归结构。例如，例5.1的递归算法对应的递归模型如下： 

f(n)=1n=1

f(n)=n*f(n-1)n>1

其中，第一个式子给出了递归的终止条件，第二个式子给出了f(n)的值与f(n-1)的值之间的关系，把第一个式子称为递归出口，把第二个式子称为递归体。
一般地，一个递归模型由递归出口和递归体两部分组成。递归出口确定递归到何时结束，即指出明确的递归结束条件。递归体确定递归求解时的递推关系。
递归出口的一般格式如下： 

f(s1)=m1

这里的s1与m1均为常量。有些递归问题可能有几个递归出口。递归体的一般格式如下： 

f(sn)=g(f(si)，f(si+1)，…，f(sn-1)，cj，cj+1，…，cm)

其中，n、i、j、m均为正整数。这里的sn是一个递归“大问题”，si、si+1、……、sn-1为递归“小问题”，cj、cj+1、……、cm是若干个可以直接(用非递归方法)解决的问题，g是一个非递归函数，可以直接求值。
实际上，递归思路是把一个不能或不好直接求解的“大问题”转换成一个或几个“小问题”来解决（如图5.2所示），再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。



图5.2把大问题f(sn)转换成几个小问题来解决




视频讲解


5.1.4递归与数学归纳法
数学归纳法是一种数学证明方法，通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立。先看一个简单示例，采用数学归纳法证明下式： 
1+2+…+n=n(n+1)/2
其证明过程如下： 
(1) 当n=1时，左式=1，右式=(1×2)/2=1，左、右两式相等，等式成立。
(2) 假设当n=k-1时等式成立，有1+2+…+(k-1)=k(k-1)/2。
(3) 当n=k时，左式=1+2+…+k=［1+2+…+(k-1)］+k=k(k-1)/2+k=k(k+1)/2=右式。

等式成立，即证。
数学归纳法证明问题的过程分为两个步骤，先考虑特殊情况，然后假设n=k-1成立(第二数学归纳法是假设n≤k-1成立)，再证明n=k时成立，即假设“小问题”成立，再推导出“大问题”成立。
递归模型中的递归体就是表示“大问题”和“小问题”解之间的关系，如果已知si、si+1、……、sn-1这些“小问题”的解，就可以计算出sn“大问题”的解。从数学归纳法的角度来看，这相当于数学归纳法的归纳步骤，只不过数学归纳法是一种论证方法，而递归是算法和程序设计的一种实现技术，数学归纳法是递归求解问题的理论基础。
5.1.5递归的执行过程
为了讨论方便，将前面的一般化的递归模型简化如下(即将一个“大问题”分解为一个“小问题”)： 


视频讲解



f(s1)=m1

f(sn)=g(f(sn-1)，cn-1)

在求f(sn)时的分解过程是f(sn)→f(sn-1)→…→f(s2)→f(s1)。
一旦遇到递归出口，分解过程结束，开始求值过程，所以分解过程是“量变”过程，即原来的“大问题”在慢慢变小，但尚未解决，遇到递归出口后便发生了“质变”，即原递归问题便转化成直接问题。
其求值过程是f(s1)=m1→f(s2)=g(f(s1)，c1)→f(s3)=g(f(s2)，c2)→…→f(sn)=g(f(sn-1)，cn-1)。
这样f(sn)便计算出来了。因此递归的执行过程由分解和求值两部分构成，分解部分就是用递归体将“大问题”分解成“小问题”，直到递归出口为止，然后进行求值过程，即已知“小问题”，计算“大问题”。例如fun(5)的求值过程如图5.3所示。


图5.3fun(5)求值过程



在递归算法的执行中最长的递归调用的链长称为该算法的递归调用深度。例如，求n!对应的递归算法在求fun(5)时递归调用深度是5。
对于复杂的递归算法，其执行过程中可能需要循环反复地分解和求值才能获得最终解。例如，对于前面求Fibonacci数列的Fib算法，求Fib(6)的过程构成的递归树如图5.4所示，向下的实箭头表示分解，向上的虚箭头表示求值，每个方框旁边的数字是该方框的求值结果，最后求得Fib(6)为8。该递归树的高度为5，所以递归调用深度也是5。


图5.4求Fib(6)对应的递归树


那么在系统内部如何执行递归算法呢？实际上一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下： 
(1) 执行开始时，首先为递归调用建立一个工作栈，其结构包括参数、局部变量和返回地址。
(2) 每次执行递归调用之前，把递归函数的参数值和局部变量的当前值以及调用后的返回地址进栈。
(3) 每次递归调用结束后，将栈顶元素出栈，使相应的参数值和局部变量值恢复为调用前的值，然后转向返回地址指定的位置继续执行。


例如有以下程序段： 

public static int S(int n)

{return (n<=0) ? 0: S(n-1)+n;}

public static void main(String［］ args)

{System.out.printf("%d＼n",S(1));}

程序执行时使用一个栈来保存调用过程的信息，这些信息用main()、S(0)和S(1)表示，那么自栈底到栈顶保存的信息的顺序是怎样的呢？


图5.5系统栈状态


首先从main()开始执行程序，将main()信息进栈，遇到调用S(1)，将S(1)信息进栈，在执行递归函数S(1)时又遇到调用S(0)，再将S(0)信息进栈（如图5.5所示），所以自栈底到栈顶保存的信息的顺序是main()→S(1)→S(0)。



用递归算法的参数值表示状态，由于在递归算法的执行中系统栈保存了递归调用的参数值、局部变量和返回地址，所以在递归算法中一次递归调用后会自动恢复该次递归调用前的状态。例如有以下递归算法，其状态为参数n的值： 

public static void f(int n)

{if(n==0)//递归出口

return;

else//递归体

{System.out.println("Pre:n="+n);

System.out.printf("执行f(%d)＼n",n-1);

f(n-1);

System.out.println("Post: n="+n);

}

}

执行f(4)的结果如下： 

Pre: n=4

执行f(3)//递归调用f(3)

Pre: n=3

执行f(2)//递归调用f(2)

Pre: n=2

执行f(1)//递归调用f(1)

Pre: n=1

执行f(0)//递归调用f(0)

Post:n=1//恢复f(0)调用前的n值

Post:n=2//恢复f(1)调用前的n值

Post:n=3//恢复f(2)调用前的n值

Post:n=4//恢复f(3)调用前的n值

从中看出，参数n的值在每次递归调用后都自动恢复了，大家所说的递归算法参数可以自动回退(回溯)就是这个意思。但全局变量并不能自动恢复，因为在系统栈中并不保存全局变量值。
5.1.6递归算法的时空分析
从前面递归算法的执行过程看到，递归算法的执行过程不同于非递归算法，所以其时空分析也不同于非递归算法。如果非递归算法分析是定长时空分析，递归算法分析就是变长时空分析。


视频讲解


1. 递归算法的时间分析
在递归算法的时间分析中，首先给出执行时间对应的递推式，然后求解递推式得出算法的执行时间T(n)，再由T(n)得到时间复杂度。
例如，对于前面求解Hanoi问题的递归算法，求问题规模为n时的时间复杂度。求解过程是设大问题Hanoi(n，X，Y，Z)的执行时间为T(n)，则小问题Hanoi(n-1，X，Y，Z)的执行时间为T(n-1)。当n>1时，大问题分解为两个小问题和一步移动操作，大问题的执行时间为两个小问题的执行时间+1，对应的递推式如下： 

T(n)=1n=1

T(n)=2T(n-1)+1n>1
求解递推式的过程如下： 

T(n)=2T(n-1)+1=2(2T(n-2)+1)+1

=22T(n-2)+2+1=22(2T(n-3)+1)+2+1

=23T(n-3)+22+2+1

=…

=2n-1T(1)+2n-2+…+22+2+1

=2n-1=O(2n)
所以问题规模为n时的时间复杂度是O(2n)。
2. 递归算法的空间分析
对于递归算法，为了实现递归过程用到一个递归栈，所以需要根据递归深度得到算法的空间复杂度。
例如，对于前面求解Hanoi塔问题的递归算法，求问题规模为n时的空间复杂度。求解过程是设大问题Hanoi(n，X，Y，Z)的临时空间为S(n)，则小问题Hanoi(n-1，X，Y，Z)的临时空间为S(n-1)。当n>1时，大问题分解为两个小问题和一步移动操作，但第一个小问题执行后会释放其空间，释放的空间被第二个小问题使用，所以大问题的临时空间为一个小问题的临时空间+1，对应的递推式如下： 

S(n)=1n=1

S(n)=S(n-1)+1n>1
求解递推式的过程如下： 

S(n)=S(n-1)+1

=S(n-2)+1+1=S(n-2)+2

=…

=S(1)+(n-1)=1+(n-1)

=n=O(n)
所以问题规模为n时的空间复杂度是O(n)。


视频讲解


5.2递归算法的设计
5.2.1递归算法设计的步骤

递归算法设计的基本步骤是先确定求解问题的递归模型，再转换成对应的Java语言方法。由于递归模型反映递归问题的“本质”，所以前一步是关键，也是讨论的重点。
递归算法的求解过程是先将整个问题划分为若干个子问题，然后分别求解子问题，最后获得整个问题的解。这是一种分而治之的思路，通常由整个问题划分的若干子问题的求解是独立的，所以求解过程对应一棵递归树。如果在设计算法时就考虑递归树中的每一个分解/求值部分，会使问题复杂化，不妨只考虑递归树中第1层和第2层之间的关系，即“大问题”和“小问题”的关系，其他关系与之相似。
由此得出构造求解问题的递归模型(简化递归模型)的步骤如下： 
(1) 对原问题f(sn)进行分析，假设出合理的“小问题”f(sn-1)。
(2) 假设小问题f(sn-1)是可解的，在此基础上确定大问题f(sn)的解，即给出f(sn)与f(sn-1)之间的关系，也就是确定递归体(与数学归纳法中假设i=n-1时等式成立，再求证i=n时等式成立的过程相似)。
(3) 确定一个特定情况［例如f(1)或f(0)］的解，由此作为递归出口(与数学归纳法中求证i=1或i=0时等式成立相似)。
【例5.2】采用递归算法求整数数组a［0..n-1］中的最小值。
解： 假设f(a，i)，求数组元素a［0..i］(共i+1个元素)中的最小值。当i=0时有f(a，i)=a［0］； 假设f(a，i-1)已求出，显然有f(a，i)=Min(f(a，i-1)，a［i］)，其中Min()为求两个值中较小值的函数。因此得到如下递归模型： 

f(a，i)=a［0］i=0

f(a，i)=Min(f(a，i-1)，a［i］)其他

由此得到如下递归求解算法： 

public static int Min(int［］ a,int i)

{if(i==0)//递归出口

return a［0］;

else//递归体

{int min=Min(a,i-1);

if(min>a［i］) return(a［i］);

else return min;

}

}

例如，若一个数组int［］ a={3，2，1，5，4}，调用Min(a，4)返回最小元素1。


视频讲解


5.2.2基于递归数据结构的递归算法设计
具有递归特性的数据结构称为递归数据结构。递归数据结构通常是采用递归方式定义的。在一个递归数据结构中总会包含一个或者多个递归运算。
例如，正整数的定义为1是正整数，若n是正整数(n≥1)，则n+1也是正整数。从中看出，正整数就是一种递归数据结构。显然，若n是正整数(n>1)，m=n-1也是正整数，也就是说对于大于1的正整数n，n-1是一种递归运算。
所以在求n!的算法中，递归体f(n)=n*f(n-1)是可行的，因为对于大于1的n，n和n-1都是正整数。
一般地，对于如下递归数据结构： 

RD=(D，Op)

D={di }(1≤i≤n，共n个元素)为构成该数据结构的所有元素的集合，Op是递归运算的集合，Op={opj }(1≤j≤m，共m个运算)，对于di∈D，不妨设opj为一元运算符，则有opj(di)∈D，也就是说递归运算具有封闭性。
在上述正整数的定义中，D是正整数的集合，Op={op1，op2}由两个基本递归运算符构成，op1的定义为op1(n)=n-1(n>1)； op2的定义为op2(n)=n+1(n≥1)。
对于不带头结点的单链表head(head结点为首结点)，其结点类型为LinkNode，每个结点的next成员为LinkNode类型的指针。这样的单链表通过首结点指针来标识。采用递归数据结构的定义如下： 


SL=(D，Op)

其中，D是由部分或全部结点构成的单链表的集合(含空单链表)，Op={op}，op的定义如下： 

op(head)=head.next//head为含一个或以上结点的单链表

显然这个递归运算符是一元运算符，且具有封闭性。也就是说，若head为不带头结点的非空单链表，则head.next也是一个不带头结点的单链表。
实际上，构造递归模型中的第2步是用于确定递归体。在假设原问题f(sn)合理的“小问题”f(sn-1)时，需要考虑递归数据结构的递归运算。例如，在设计不带头结点的单链表的递归算法时，通常设sn为以head为首结点的整个单链表，sn-1为除首结点外余下结点构成的单链表(由head.next标识，其中的'.next'运算为递归运算)。
【例5.3】假设有一个不带头结点的单链表p，完成以下两个算法设计： 
(1) 设计一个算法正向输出所有结点值。
(2) 设计一个算法反向输出所有结点值。
解： (1) 设f(p)的功能是正向输出单链表p的所有结点值，即输出a1~an，为大问题。小问题f(p.next)的功能是输出a2~an，如图5.6所示。对应的递归模型如下： 

f(p)≡不做任何事件p=null

f(p)≡输出p结点值; f(p.next)其他



图5.6正向输出head的所有结点值


其中，“≡”表示功能等价关系。对应的递归算法如下： 

public static void Positive(LinkNode<Integer> p)

{if(p==null) return;

else

{System.out.print(p.data+" ");

Positive(p.next);

}

}


(2) 设f(p)的功能是反向输出p的所有结点值，即输出an~a1，为大问题。小问题f(p.next)的功能是输出an~a2，如图5.7所示。对应的递归模型如下： 

f(p)≡不做任何事件p=null

f(p)≡f(p.next);输出p结点值其他



图5.7一个不带头结点的单链表


对应的递归算法如下： 

public static void Reverse(LinkNode<Integer> p)

{if(p==null) return;

else

{Reverse(p.next);

System.out.print(p.data+" ");

}

}

从中可以看出，两个算法的功能完全相反，但在算法设计上仅仅是两行语句的顺序不同，而且两个算法的时间复杂度和空间复杂度完全相同。如果采用第2章的遍历方法，这两个算法在设计上有较大的差异。
说明： 在设计单链表的递归算法时通常采用不带头结点的单链表，这是因为小问题处理的单链表不可能带头结点，大问题处理的单链表需要在结构上相同，所以整个单链表也不应该带头结点。实际上，若单链表对象L是带头结点的，则L.head.next就看成是一个不带头结点的单链表。


所以在对采用递归数据结构存储的数据设计递归算法时，通常先对该数据结构及其递归运算进行分析，从而设计出正确的递归体，再假设一种特殊情况，得到对应的递归出口。
5.2.3基于归纳方法的递归算法设计
基于归纳方法的递归算法设计是指通过对求解问题的分析归纳来转换成递归方法求解(例如皇后问题等)。
例如，有一个位数为n的十进制正整数x，求所有数位的和，如果x=123，结果为1+2=3=6。
不妨将x表示为x=xn-1xn-2…x1x0，设大问题f(x)=xn-1+xn-2+…+x1+x0(n≥1)，由于y=x/10= xn-1xn-2…x1，x%10=x0，所以对应的小问题为f(y)=xn-1+xn-2+…+x1。假设小问题是可求的，则f(x)=f(x/10)+x%10。特殊情况是x的位数为1，此时结果就是x。对应的递归模型如下： 
f(x)=xx为一位整数

f(x)=f(x/10)+x%10其他
对应的递归算法如下： 

public static int Sum(int x)

{if (x>=0 && x<=9) return x;

else return Sum(x/10)+x%10;

}

从中可以看出，在采用递归方法求解时关键是对问题本身进行分析，确定大、小问题解之间的关系，构造出合理的递归体，而其中最重要的又是假设出“合理”的小问题。对于上一个问题，如果假设小问题f(y)=xn-2+xn-3+…+x0，就不如假设小问题f(y)=xn-1+xn-2+…+x1简单。
*【例5.4】若算法pow(x，n)用于计算xn(n为大于1的整数)，完成以下任务： 
(1) 采用递归方法设计pow(x，n)算法。
(2) 问执行pow(x，5)发生几次递归调用？求pow(x，n)对应的算法复杂度是多少？
(3) 设计相应的非递归算法pow1(x，n)。


视频讲解


解： (1) 设f(x，n)用于计算xn，则有以下递归模型。

f(x，n)=1n=0

f(x，n)=x*f(x，n/2)*f(x，n/2)n为奇数

f(x，n)=f(x，n/2)*f(x，n/2)n为偶数

对应的递归算法如下： 

public static double pow(double x,int n)

{if(n==0) return 1;

double p=pow(x,n/2);

if(n%2==1) return x*p*p;//n为奇数

else return p*p;//n为偶数

}

(2) 执行pow(x，5)的递归调用顺序是pow(x，5)→pow(x，2)→pow(x，1)→pow(x，0)，共发生4次递归调用。求pow(x，n)对应的算法复杂度是O(log2n)。
(3) 为了计算xn，可以将n拆成二进制数，该二进制数的第i位的权为2i-1，例如当n=11时，其二进制数是［1011］2，即11=23×1+22×0+21×1+20×1，因此可以将x11转化为计算x2^0×x2^1×x2^3，也就是x11=x1×x2×x8。
用ans存放计算结果，先置ans=1，base=x，当n>0时循环： 取n的末尾二进制数，若为0则跳过，若为1则执行ans*=base，再执行base*=base，并且将n右移一位。最后返回ans。简单地说，base为权，按x、x2、x4……递增，当对应二进制位为1时，ans乘上相应的base。该算法称为快速幂算法。
对应的非递归算法如下： 

public static double pow1(double x,int n)

{double ans=1.0,base=x;

while(n!=0)

{if((n&1)==1)//遇到二进制位1

ans*=base;//求ans

base*=base;//权递增

n >>= 1;//n右移1位

}

return ans;

}



视频讲解


【例5.5】创建一个n阶螺旋矩阵并输出。例如，n=4时的螺旋矩阵如下： 

1234

1213145

1116156

10987

解： 设f(x，y，start，n)用于创建左上角为(x，y)、起始元素值为start的n阶螺旋矩阵，如图5.8所示，共n行n列，它是大问题。f(x+1，y+1，start，n-2)用于创建左上角为(x+1，y+1)、起始元素值为start的n-2阶螺旋矩阵，共n-2行n-2列，它是小问题。例如，如果4阶螺旋矩阵为大问题，那么2阶螺旋矩阵就是一个小问题，如图5.9所示。
对应的递归模型(大问题的start从1开始)如下： 

f(x，y，start，n)≡不做任何事情n≤0

f(x，y，start，n)≡产生只有一个元素的螺旋矩阵n=1

f(x，y，start，n)≡产生(x，y)的那一圈n>1

f(x+1，y+1，start，n-2)



图5.8n阶螺旋矩阵




图5.9n=4时的大问题和小问题


对应的完整程序如下： 

public class Exam5_5

{static int N=15;

static int［］［］ s=new int［N］［N］;

static int n;

public static void Spiral(int x,int y,int start,int n)//递归创建螺旋矩阵

{if(n<=0) return;//递归结束条件

if(n==1)//矩阵大小为1时

{s［x］［y］=start;

return;

}

for(int j=x;j<x+n-1;j++)//上一行

s［y］［j］=start++;

for(int i=y;i<y+n-1;i++)//右一列

s［i］［x+n-1］=start++;

for(int j=x+n-1;j>x;j--)//下一行

s［y+n-1］［j］= start++;

for(int i=y+n-1;i>y; i--)//左一列

s［i］［x］=start++;

Spiral(x+1,y+1,start,n-2);//递归调用

}

public static void Display()//输出螺旋矩阵

{for(int i=0;i<n;i++)

{for(int j=0;j<n;j++)

System.out.printf("%4d",s［i］［j］);

System.out.println("");

}

}

public static void main(String［］ args)

{n=5;

Spiral(0,0,1,n);

Display();

}

}

*【例5.6】采用递归算法求解迷宫问题，输出从入口到出口的所有迷宫路径。
解： 迷宫问题在第3章中介绍过，设mgpath(int xi，int yi，int xe，int ye，path)是求从(xi，yi)到(xe，ye)的迷宫路径，用path变量保存一条迷宫路径，它是元素为Box类型的ArrayList对象，其中类Box定义如下： 


视频讲解



class Box//方块类

{int i;//方块的行号

int j;//方块的列号

public Box(int i1,int j1)//构造方法

{i=i1; j=j1; }

}

当从(xi，yi)方块找到一个相邻可走方块(i，j)后，mgpath(i，j，xe，ye，path)表示求从(i，j)到出口(xe，ye)的迷宫路径。显然，mgpath(xi，yi，xe，ye，path)是“大问题”，而mgpath(i，j，xe，ye，path)是“小问题”(即大问题=试探一步+小问题)，如图5.10所示。求解上述迷宫问题的递归模型如下： 


图5.10大、小问题的关系


mgpath(xi,yi,xe,ye,path) ≡将(xi,yi)添加到path中; 若(xi,yi)=(xe,ye)，即找到出口

置mg［xi］［yi］=-1;

输出path中的迷宫路径;

恢复出口迷宫值为0,即置mg［xe］［ye］=0
mgpath(xi,yi,xe,ye,path) ≡将(xi,yi)添加到path中;若(xi,yi)不是出口

置mg［xi］［yi］=-1;

对于(xi,yi)的每个相邻可走方块(i,j)，调用mg(i,j,xe,ye,path);

path回退一步并置mg［xi］［yi］=0;
在上述递归模型中，对于方块(xi，yi)，先添加到path末尾(所有path中的方块都是通道，所以初始调用时入口必须是通道)，对于它的每一个相邻可走方块(i，j)都执行“小问题”mgpath(i，j，xe，ye，path)，之后需要从(xi，yi)方块回退(删除path中的末尾方块)并置mg［xi］［yi］为0，其目的是恢复前面求迷宫路径而改变的环境，以便找出所有的迷宫路径。


以第3章中图3.13所示的迷宫为例，求从入口(1，1)到出口(4，4)的所有迷宫路径的完整程序如下： 

import java.lang.*;

import java.util.*;

class Box//方块类

{int i;//方块的行号

int j;//方块的列号

public Box(int i1,int j1)//构造方法

{i=i1; j=j1; }

}

class MazeClass//求解迷宫路径类

{final int MaxSize=20;

int［］［］ mg;//迷宫数组

int m,n;//迷宫的行列数

int cnt=0;//累计迷宫路径数

public MazeClass(int m1,int n1)//构造方法

{m=m1;

n=n1;

mg=new int［MaxSize］［MaxSize］;

}

public void Setmg(int［］［］ a)//设置迷宫数组

{for(int i=0;i<m;i++)

for(int j=0;j<n;j++)

mg［i］［j］=a［i］［j］;

}

void mgpath(int xi,int yi,int xe,int ye,ArrayList<Box> path)//求解迷宫路径为(xi,yi)>(xe,ye)

{Box b;

int di,i=0,j=0;

b=new Box(xi,yi);

path.add(b);//将(xi,yi)添加到path中

mg［xi］［yi］=-1;//mg［xi］［yi］=-1

if(xi==xe && yi==ye)//找到了出口,输出一个迷宫路径

{System.out.printf("迷宫路径%d:",++cnt);//输出path中的迷宫路径

for(int k=0;k<path.size();k++)

System.out.printf("(%d,%d)",path.get(k).i,path.get(k).j);

System.out.println();

mg［xi］［yi］=0;//恢复为0,否则其他路径找不到出口

}

else//(xi,yi)不是出口

{di=0;

while(di<4)//处理(xi,yi)四周的每个相邻方块(i,j)

{switch(di)

{

case 0:i=xi-1;j=yi;break;

case 1:i=xi;j=yi+1;break;

case 2:i=xi+1;j=yi;break;

case 3:i=xi;j=yi-1;break;

}

if(mg［i］［j］==0)//(i,j)可走时

mgpath(i,j,xe,ye,path);//从(i,j)出发查找迷宫路径

di++;//继续处理(xi,yi)的下一个相邻方块

}

}

path.remove(path.size()-1);//删除path中的末尾方块(回退一个方块)

mg［xi］［yi］=0;

}

}

public class Exam5_6

{public static void main(String［］ args)

{int［］［］ a= { {1,1,1,1,1,1},{1,0,1,0,0,1},

{1,0,0,1,1,1},{1,0,1,0,0,1},

{1,0,0,0,0,1},{1,1,1,1,1,1} };

MazeClass mz=new MazeClass(6,6);

ArrayList<Box> path=new ArrayList<Box>();

mz.Setmg(a);

mz.mgpath(1,1,4,4,path);

}

}

上述程序的执行结果如下： 

迷宫路径1: (1,1)(2,1)(3,1)(4,1)(4,2)(4,3)(3,3)(3,4)(4,4)

迷宫路径2: (1,1)(2,1)(3,1)(4,1)(4,2)(4,3)(4,4)

本例求出了所有的迷宫路径，可以通过路径长度的比较求出最短迷宫路径(可能存在多条最短迷宫路径)。
5.3练习题
5.3.1问答题

1. 两个非负整数a和b相加时，若b为0，则结果为a，利用Java语言中的“++”和“--”运算符给出其递归定义。
2. 求两个正整数的最大公约数(gcd)的欧几里得定理是对于两个正整数a和b，当a>b并且a%b=0时最大公约数为b，否则最大公约数等于其中较小的那个数和两数相除余数的最大公约数。请给出对应的递归模型。
3. 有以下递归函数： 

public static void fun(int n)

{if(n==1)

System.out.printf("a:%d＼n",n);

else

{System.out.printf("b:%d＼n",n);

fun(n-1);

System.out.printf("c:%d＼n",n);

}

}

分析调用fun(5)的输出结果。
4. 有如下递归函数fact(n)，求问题规模为n时的时间复杂度和空间复杂度。

int fact(int n)

{if(n<=1)

return 1;

else

return n*fact(n-1);

}

5.3.2算法设计题
1. 角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。设计一个递归算法求经过多少次可得到自然数1。例如输入22，输出STEP=16，即自然数22经过16次可得到自然数1。
2. 对于含n个整数的数组a［0..n-1］，可以这样求最大元素值： 
(1) 若n=1，则返回a［0］。
(2) 否则取中间位置mid，求出前半部分中的最大元素值max1，求出后半部分中的最大元素值max2，返回max(max1，max2)。
给出实现上述过程的递归算法。
3. 设有一个不带表头结点的整数单链表p，设计一个递归算法getno(p，x)查找第一个值为x的结点的序号(假设首结点的序号为0)，没有找到时返回-1。
4. 设有一个不带表头结点的整数单链表p，设计两个递归算法，maxnode(p)返回单链表p中的最大结点值，minnode(p)返回单链表p中的最小结点值。
5. 设有一个不带表头结点的整数单链表p，设计一个递归算法replace(p，x，y)将单链表p中所有值为x的结点替换为y。
6. 设有一个不带表头结点的整数单链表p，设计两个递归算法，delx(p，x)删除单链表p中第一个值为x的结点，delxall(p，x)删除单链表p中所有值为x的结点。
5.4实验题
5.4.1上机实验题

1. Fibonacci数列递归算法的改进。5.1.2节中求Fibonacci数列的递归算法Fib1(n)是低效的，包含大量重复的计算，请仍然采用递归改进该算法，并且输出n=40时两个算法的执行时间。
2. 求楼梯走法数问题。一个楼梯有n个台阶，上楼可以一步上一个台阶，也可以一步上两个台阶，编写一个实验程序求上楼梯共有多少种不同的走法。
3. 求解皇后问题。在n×n的方格棋盘上放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线，编写一个实验程序求n皇后的所有解。
5.4.2在线编程题
1. POJ1664——放苹果

时间限制： 1000ms； 空间限制： 10000KB。
问题描述： 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法(用k表示)？注意5，1，1和1，5，1是同一种分法。
输入格式： 第一行是测试数据的数目t(0≤t≤20)，以下每行均包含两个整数m和n，以空格分开，1≤m，n≤10。
输出格式： 对于输入的每组数据m和n，用一行输出相应的k。
输入样例： 

1

7 3

输出样例： 

8

2. POJ2083——分形问题
时间限制： 1000ms； 空间限制： 30000KB。
问题描述： 分形是从某种技术意义上在所有尺度上以自相似方式显示的物体或数值。物体不需要在所有尺度上都具有完全相同的结构，但在所有尺度上必须具有相同的结构“类型”。盒子分形的定义如下： 
1级盒子分形是简单的： 

X

2级盒子分形是： 

XX

X

XX

如果用B(n-1)表示n-1级盒子分形，那么递归地定义n级盒子分形如下： 

B(n-1)B(n-1)

B(n-1)

B(n-1)B(n-1)
请画出n级盒子分形。
输入格式： 输入包含几个测试用例。输入的每一行包含一个不大于7的正整数n，输入的最后一行是负整数-1，表示输入结束。
输出格式： 对于每个测试用例，使用X表示法输出框分形。注意X是一个大写字母。在每个测试用例后打印一行，该行只有一个短画线。
输入样例： 

1

2

3

4

-1

输出样例： 输出结果如图5.11所示。



图5.11样例的输出结果


3. HDU2021——发工资问题
时间限制： 2000ms； 空间限制： 65536KB。
问题描述： 作为学校的老师，最盼望的日子就是每月的8号了，但是对于学校财务处的工作人员来说，这一天则是很忙碌的一天。财务处的小胡老师最近在考虑一个问题： 如果知道每个老师的工资额，最少需要准备多少张人民币才能在给每位老师发工资的时候不用老师找零呢？这里假设老师的工资都是正整数，单位为元，人民币一共有100元、50元、10元、5元、2元和1元6种。
输入格式： 输入数据包含多个测试用例，每个测试用例的第一行是一个整数n(n<100)，表示老师的人数，然后是n个老师的工资。n=0表示输入结束，不做处理。
输出格式： 对于每个测试用例输出一个整数x，表示最少需要准备的人民币张数。每个输出占一行。
输入样例： 

3

1 2 3

0

输出样例： 

4

4. HDU1997——汉诺塔问题
时间限制： 2000ms； 空间限制： 65536KB。
问题描述： n个盘子的Hanoi塔问题的最少移动次数是2n-1，即在移动过程中会产生2n个系列。由于发生错移产生的系列增加了，这种错误是放错了柱子，并不会把大盘放到小盘上，即各柱子从下往上的大小仍保持如下关系： 
n=m+p+q

a1>a2>…>am

b1>b2>…>bp

c1>c2>…>cq

其中ai是A柱上的盘子的盘号系列，bi是B柱上的盘子的盘号系列，ci是C柱上的盘子的盘号系列，最初目标是将A柱上的n个盘子移到C盘。给出一个系列，判断它是否为在正确移动中产生的系列。
例1，n=3

3//A柱上只有盘号为3的盘子

2//B柱上只有盘号为2的盘子

1//C柱上只有盘号为1的盘子

是正确的。而例2，n=3

3//A柱上只有盘号为3的盘子

1//B柱上只有盘号为1的盘子

2//C柱上只有盘号为2的盘子

是不正确的。
注意： 对于例2，如果目标是将A柱上的n个盘子移到B盘，则是正确的。
输入格式： 包含多组数据，首先输入t，表示有t组数据，每组数据4行，第一行n是盘子的数目，n≤64，后3行如下： 

m a1 a2 … am

p b1 b2 … bp

q c1 c2 … cq

其中，n=m+p+q，0≤m≤n，0≤p≤n，0≤q≤n。
输出格式： 对于每组数据，判断它是否为在正确移动中产生的系列，正确时输出true，否则输出false。
输入样例： 

6

3

1 3

1 2

1 1

3

1 3

1 1

1 2

6

3 6 5 4

1 1

2 3 2

6

3 6 5 4

2 3 2

1 1

3

1 3

1 2

1 1

20

2 20 17

2 19 18

16 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

输出样例： 

true

false

false

false

true

true

5. HDU2013——蟠桃记问题
时间限制： 2000ms； 空间限制： 65536KB。
问题描述： 喜欢《西游记》的同学肯定都知道悟空偷吃蟠桃的故事，读者一定觉得这猴子太闹腾了，其实读者是有所不知，悟空是在研究一个数学问题！什么问题？他研究的问题是蟠桃一共有多少个。不过，到最后他还是没能解决这个难题。当时的情况是这样的： 第一天悟空吃掉桃子总数的一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。请帮悟空算一下，他第一天开始吃的时候桃子一共有多少个？
输入格式： 输入数据有多组，每组占一行，包含一个正整数n(1<n<30)，表示只剩下一个桃子的时候是在第n天发生的。
输出格式： 对于每组输入数据，输出第一天开始吃的时候桃子的总数，每个测试用例占一行。
输入样例： 

2

4

输出样例： 

4

22

6. POJ1979——红与黑问题
时间限制： 1000ms； 空间限制： 30000KB。
问题描述： 一间长方形客房铺有方形瓷砖，每块瓷砖为红色或黑色。一个男人站在黑色瓷砖上，他可以移动到4个相邻瓷砖中的一个，但他不能在红色瓷砖上移动，只能在黑色瓷砖上移动。编写一个程序，通过重复上述动作来计算他可以到达的黑色瓷砖的数量。
输入格式： 输入由多个数据集组成。数据集以包含两个正整数W和H的行开始，W和H分别是x和y方向上的瓷砖数量，W和H不超过20，数据集中还有H行，每行包含W个字符。每个字符代表的内容如下： 
(1) '.'代表黑色瓷砖。
(2) '#'代表红色瓷砖。
(3) '@'代表黑色瓷砖上的男人(在一个数据集中只出现一次)。
输入的结尾由两个0组成的行表示。
输出格式： 对于每个数据集，编写的程序应输出一行，其中包含该男人可以从初始瓷砖(包括其自身)到达的瓷砖的数量。
输入样例： 

6 9

....#.

.....#

......

......

......

......

......

#@...#

.#..#.

11 9

.#.........

.#.#######.

.#.#.....#.

.#.#.###.#.

.#.#..@#.#.

.#.#####.#.

.#.......#.

.#########.

...........

11 6

..#..#..#..

..#..#..#..

..#..#..###

..#..#..#@.

..#..#..#..

..#..#..#..

7 7

..#.#..

..#.#..

###.###

...@...

###.###

..#.#..

..#.#..

0 0

输出样例： 

45

59

6

13

7.  POJ3752——字母旋转游戏
时间限制： 1000ms； 空间限制： 65536KB。
问题描述： 给定两个整数m、n，生成一个m×n的矩阵，矩阵中元素的取值为A~Z的26个字母中的一个，A在左上角，其余各数按顺时针方向旋转前进，依次递增放置，当超过26时又从A开始填充。例如，当m=5、n=8时矩阵中的内容如图5.12所示。


图5.12m=5、n=8时的矩阵


输入格式： m为行数，n为列数，其中m、n都为大于0的整数。
输出格式： 分行输出相应的结果。
输入样例： 

4 9

输出样例： 

ABCDEFGHI

VWXYZABCJ

UJIHGFEDK

TSRQPONML