C H A P T E R5

第5章
递归




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



视频讲解


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

在定义一个过程或函数时出现调用本过程或本函数的成分，称为递归。若调用自身，称为直接递归。若过程或函数A调用过程或函数B，而B又调用A，称为间接递归。在算法设计中，任何间接递归算法都可以转换为直接递归算法来实现，所以后面主要讨论直接递归。

递归不仅是数学中的一个重要概念，也是计算技术中重要的概念之一。在计算技术中，与递归有关的概念有递归数列、递归过程、递归算法、递归程序和递归方法等。

如果在一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。
【例5.1】
以下是求n!(n为正整数)的递归函数，它属于什么类型的递归？

def fun(n):

if n==1:#语句1

return 1#语句2

else:#语句3

return fun(n-1)*n#语句4

解： 在函数fun(n)的求解过程中调用fun(n-1)(语句4)，它是一个直接递归函数。又由于递归调用是最后一条语句，所以它又属于尾递归。

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





视频讲解


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

def Fib(n): #求Fibonacci数列的第n项

if n==1 or n==2:

return 1

else:

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

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

class LinkNode:#单链表结点类

def __init__(self,data=None):#构造函数

self.data=data#dat属性

self.next=None#next属性

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

def Sum(p):#求不带头结点单链表p中所有结点值之和

if p==None:

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递归算法如下： 

def Hanoi(n,X,Y,Z):#Hanoi递归算法

if n==1:#只有一个盘片的情况

print("将第%d个盘片从%c移动到%c" %(n,X,Z))

else:#有两个或多个盘片的情况

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

print("将第%d个盘片从%c移动到%c" %(n,X,Z))

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

调用Hanoi(3,'X','Y','Z')的输出结果如下： 

将第1个盘片从X移动到Z

将第2个盘片从X移动到Y

将第1个盘片从Z移动到Y

将第3个盘片从X移动到Z

将第1个盘片从Y移动到X

将第2个盘片从Y移动到Z

将第1个盘片从X移动到Z




视频讲解


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

f(n)=1n=1

f(n)=nf(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


其证明过程如下： 

① 当n=1时，左式=1，右式=(1×2)/2=1，左、右两式相等，等式成立。
② 假设当n=k-1时等式成立，有1+2+…+(k-1)=k(k-1)/2。
③ 当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)对应的递归树


那么在系统内部如何执行递归算法呢？实际上一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下。

① 执行开始时，首先为递归调用建立一个工作栈，其结构包括参数、局部变量和返回地址。
② 每次执行递归调用之前，把递归函数的参数和局部变量的当前值以及调用后的返回地址进栈。
③ 每次递归调用结束后，将栈顶元素出栈，使相应的参数值和局部变量值恢复为调用前的值，然后转向返回地址指定的位置继续执行。

例如有以下程序段： 

def S(n):

if n<=0: return 0

else: return S(n-1)+n



def main():

print(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的值： 

def f(n):#递归函数

if (n==0):#递归出口

return

else:#递归体

print("Pre:n=%d" %(n))

print("执行f(%d)" %(n-1))

f(n-1)

print("Post: n=%d" %(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.6Python中递归函数的参数

Python递归函数中的参数分为可变类型和不可变类型，实际上只有不可变类型的参数才保存在系统栈中，具有自动回退的功能，而可变类型的参数类似全局变量，不具有自动回退的功能。例如有以下fun()函数，其中形参i为整数(不可变类型)，lst为列表(可变类型)，每次调用时输出它们的地址： 

def fun(i,lst):

print(id(i),id(lst))

if i>=0:

print(lst［i］,end=' ')

fun(i-1,lst)

#主程序

L=［1,2,3］

fun(len(L)-1,L)

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

15184949121721848

315184948961721848

215184948801721848

115184948641721848

从中看到，每次递归调用fun()时形参i的地址均不同，而lst的地址始终是一样的，所以完全可以直接用全局变量lst替代形参lst，对应的程序如下： 

lst=［1,2,3］

def fun(i):

print(id(i),id(lst))

if i>=0:

print(lst［i］,end=' ')

fun(i-1)

#主程序

fun(len(lst)-1)




视频讲解


5.1.7递归算法的时空分析

从前面递归算法的执行过程看到，递归算法的执行过程不同于非递归算法，所以其时空分析也不同于非递归算法。如果非递归算法分析是定长时空分析，递归算法分析就是变长时空分析。
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递归算法设计的步骤


递归算法设计的基本步骤是先确定求解问题的递归模型，再转换成对应的Python语言方法。由于递归模型反映递归问题的“本质”，所以前一步是关键，也是讨论的重点。

递归算法的求解过程是先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。这是一种分而治之的思路，通常由整个问题划分的若干子问题的求解是独立的，所以求解过程对应一棵递归树。如果在设计算法时就考虑递归树中每一个分解/求值部分，会使问题复杂化。不妨只考虑递归树中第1层和第2层之间的关系，即“大问题”和“小问题”的关系，其他关系与之相似。
由此得出构造求解问题的递归模型(简化递归模型)的步骤如下。

① 对原问题f(sn)进行分析，假设出合理的“小问题”f(sn-1)。
② 假设小问题f(sn-1)是可解的，在此基础上确定大问题f(sn)的解，即给出f(sn)与f(sn-1)之间的关系，也就是确定递归体(与数学归纳法中假设i=n-1时等式成立，再求证i=n时等式成立的过程相似)。

③ 确定一个特定情况(例如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］)其他


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

def Min(a,i):#求a［0..i］中的最小值

if i==0:#递归出口

return a［0］

else:#递归体

min=Min(a,i-1)

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

else: return min


例如，若一个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)=nf(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的所有结点值，即输出a0~an-1，为大问题。小问题f(p.next)的功能是输出a1~an-1，如图5.6所示。对应的递归模型如下： 



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

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





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


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

def Positive(p):#正向输出所有结点值

if p==None:

return

else:

print("%d" %(p.data),end=' ')

Positive(p.next)



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



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

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





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


对应的递归算法如下： 

def Reverse(p):#反向输出所有结点值

if p==None:

return

else:

Reverse(p.next)

print("%d" %(p.data),end=' ')


从中看出，两个算法的功能完全相反，但算法在设计上仅两行语句的顺序不同，而且两个算法的时间复杂度和空间复杂度完全相同。如果采用第2章的遍历方法，这两个算法在设计上有较大的差异。


说明： 在设计单链表的递归算法时，通常采用不带头结点的单链表，这是因为小问题处理的单链表不可能带头结点，大、小问题处理的单链表需要在结构上相同，所以整个单链表也不应该带头结点。实际上，若单链表对象L是带头结点的，则L.head.next就看成是一个不带头结点的单链表。

所以在对采用递归数据结构存储的数据设计递归算法时，通常先对该数据结构及其递归运算进行分析，从而设计出正确的递归体，再假设一种特殊情况，得到对应的递归出口。

5.2.3基于归纳方法的递归算法设计

通过对求解问题的分析归纳转换成递归方法求解(如n皇后问题等)。



视频讲解


例如有一个位数为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其他


对应的递归算法如下： 

def Sum(x):#求整数x的所有数位的和

if x>=0 and x<=9:

return x

else:

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


从中看出，在采用递归方法求解时，关键是对问题本身进行分析，确定大、小问题解之间的关系，构造合理的递归体，而其中最重要的又是假设出“合理”的小问题。对于上一个问题，如果假设小问题f(y)=xn-2+xn-2+…+x0，就不如假设小问题f(y)=xn-1+xn-2+…+x1简单。

【例5.4】
若算法pow(x，n)用于计算xn(n为大于1的整数)，完成以下任务： 

(1) 采用递归方法设计pow(x，n)算法。
(2) 问执行pow(x，10)发生几次递归调用？求pow(x，n)对应的算法复杂度是多少？
解： (1) 设f(x，n)用于计算xn，则有以下递归模型。




f(x，n)=xn=1

f(x，n)=x*f(x，n/2)*f(x，n/2)n为大于1的奇数

f(x，n)=f(x，n/2)*f(x，n/2)n为大于1的偶数


对应的递归算法如下： 

def pow(x,n):#求x的n次幂

if n==1:

return x

p=pow(x,n//2)

if n%2==1:

return x*p*p#n为奇数

else:

return p*p#n为偶数


(2) 执行pow(x，10)的递归调用顺序是pow(x，10)→pow(x，5)→pow(x，2)→pow(x，1)，共发生4次递归调用。求pow(x，n)对应的算法复杂度是O(log2n)。
【例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所示。



图5.8n阶螺旋矩阵





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



对应的递归模型(大问题的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)


对应的完整程序如下： 

N=15

a=［［0］*N for i in range(N)］#存放螺旋矩阵

def Spiral(x,y,start,n):#递归创建螺旋矩阵

if n<=0: return#递归结束条件

if n==1:#矩阵大小为1时

a［x］［y］=start

return

for j in range(x,x+n-1):#上一行

a［y］［j］=start

start+=1

for i in range(y,y+n-1):#右一列

a［i］［x+n-1］=start

start+=1

for j in range(x+n-1,x,-1):#下一行

a［y+n-1］［j］=start

start+=1

for i in range(y+n-1,y,-1):#左一列

a［i］［x］=start

start+=1

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



#主程序

n=4

Spiral(0,0,1,n)

for i in range(0,n):

for j in range(0,n):

print("%3d" %(a［i］［j］),end=' ')

print()

【例5.6】采用递归算法求解迷宫问题，输出从入口到出口的所有迷宫路径。

解： 迷宫问题在第3章介绍过，这里用path［0..d］数组存放迷宫路径(d为整数，表示路径中最后一个方块的索引)，其中的元素［i，j］为迷宫路径上的方块。


视频讲解


设mgpath(xi，yi，xe，ye，path，d)是求从入口(xi，yi)到出口(xe，ye)的所有迷宫路径，是“大问题”，当从(xi，yi)方块找到一个相邻可走方块(i，j)后，mgpath(i，j，xe，ye，path，d)表示求从(i，j)到出口(xe，ye)的所有迷宫路径，是“小问题”，则有大问题=走一步+小问题，如图5.10所示。



图5.10大、小问题的关系


求解上述迷宫问题的递归模型如下： 

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

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

输出path中的迷宫路径;

恢复出口迷宫值为0，即置mg［xe］［ye］=0

mgpath(xi,yi,xe,ye,path,d)≡d++; 将(xi,yi)添加到path中;若(xi,yi)不是出口

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

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

从(xi,yi)回退一步，即置mg［xi］［yi］=0;


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

mg=［［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］］

dx=［-1,0,1,0］#x方向的偏移量

dy=［0,1,0,-1］#y方向的偏移量

cnt=0 #累计迷宫路径数

def mgpath(xi,yi,xe,ye,path,d):#求解迷宫路径为(xi,yi)>(xe,ye)

global cnt

d+=1; path［d］=［xi,yi］#将(xi,yi)方块对象添加到路径中

mg［xi］［yi］=-1#mg［xi］［yi］=-1

if xi==xe and yi==ye:#找到了出口，输出一个迷宫路径

cnt+=1

print("迷宫路径%d: " %(cnt),end='')#输出第cnt条迷宫路径

for k in range(d+1):

print("(%d,%d)" %(path［k］［0］,path［k］［1］),end=' ')

print()

mg［xi］［yi］=0#从出口回退，恢复其mg值

return

else:#(xi,yi)不是出口

di=0

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

i,j=xi+dx［di］,yi+dy［di］#找(xi,yi)的di方位的相邻方块(i,j)

if mg［i］［j］==0:#若(i,j)可走

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

di+=1#继续处理(xi,yi)的下一个相邻方块

mg［xi］［yi］=0#(xi,yi)的所有相邻方块处理完，回退并恢复mg值



#主程序

xi,yi=1,1

xe,ye=4,4

print("［%d,%d］到［%d,%d］的所有迷宫路径:" %(xi,yi,xe,ye))

path=［None］*100

d=-1

mgpath(xi,yi,xe,ye,path,d)

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

［1,1］到［4,4］的所有迷宫路径:

迷宫路径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练习题

1. 求两个正整数的最大公约数(gcd)的欧几里得定理是，对于两个正整数a和b，当a>b并且a%b=0时，最大公约数为b，否则最大公约数等于其中较小的那个数和两数相除余数的最大公约数。请给出对应的递归模型。
2. 有以下递归函数： 

def fun(n):

if n==1:

print("a:%d" %(n))

else:

print("b:%d" %(n))

fun(n-1)

print("c:%d" %(n))

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

def fact(n):

if n<=1:

return 1

else:

return n*fact(n-1)


4. 对于含n个整数的数组a［0..n-1］，可以这样求最大元素值： 
① 若n=1，则返回a［0］。

② 否则，取中间位置mid，求出前半部分中的最大元素值max1，求出后半部分中的最大元素值max2，返回max(max1，max2)。

给出实现上述过程的递归算法。

5. 设有一个不带表头结点的整数单链表p，设计一个递归算法getno(p，x)查找第一个值为x的结点的序号(假设首结点的序号为0)，没有找到时返回-1。
6. 设有一个不带表头结点的整数单链表p(所有结点值均位于1~100)，设计两个递归算法，maxnode(p)返回单链表p中的最大结点值，minnode(p)返回单链表p中的最小结点值。
7. 设有一个不带表头结点的整数单链表p，设计一个递归算法delx(p，x)删除单链表p中第一个值为x的结点。
8. 设有一个不带表头结点的整数单链表p，设计一个递归算法delxall(p，x)删除单链表p中所有值为x的结点。
5.4上机实验题
5.4.1基础实验题


1. 在求n!的递归算法中增加若干输出语句，以显示求n!时的分解和求值过程，并输出求5!的过程。

2. 采用递归算法求Fibonacci数列的第n项时存在重复计算，设计对应的非递归算法避免这些重复计算，并且输出递归和非递归算法的前10项结果。
5.4.2应用实验题
1. 求楼梯走法数问题。一个楼梯有n个台阶，上楼可以一步上一个台阶，也可以一步上两个台阶。编写一个实验程序，求上楼梯共有多少种不同的走法，并用相关数据进行测试。
2. 假设L是一个带头结点的非空单链表，设计以下递归算法： 
(1) 逆置单链表L。
(2) 求结点值为x的结点个数。

并用相关数据进行测试。

3. 输入一个正整数n(n>5)，随机产生n个1~99的整数，采用递归算法求其中的最大整数和次大整数。

5.5LeetCode在线编程题
1. LeetCode7——整数反转




视频讲解


问题描述： 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例1： 输入123，输出321。
示例2： 输入-123，输出-321。
示例3： 输入120，输出21。
假设我们的环境只能存储得下32位的有符号整数，则其数值范围为［-231,231-1］。根据这个假设，如果反转后整数溢出,就返回0。
要求设计满足题目条件的如下方法： 

def reverse(self, x：  int) > int： 




视频讲解


2. LeetCode24——两两交换链表中的结点

问题描述： 给定一个链表，两两交换其中相邻的结点，并返回交换后的链表。注意不能只是单纯地改变结点内部的值，而是需要实际地进行结点交换。例如，给定链表为1>2>3>4，返回结果为2>1>4>3。要求设计满足题目条件的如下方法： 

def swapPairs(self,head:ListNode)>ListNode:

3. LeetCode59——螺旋矩阵II

问题描述： 给定一个正整数n，生成一个包含1到n2的所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。例如输入3，输出结果如下： 



视频讲解



［

［ 1,2,3 ］,

［ 8,9,4 ］,

［ 7,6,5 ］

］

要求设计满足题目条件的如下方法： 

def generateMatrix(self,n:int)>List［List［int］］:




视频讲解


4.  LeetCode52——n皇后II

问题描述： n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数n，返回n皇后不同的解决方案的数量。要求设计满足题目条件的如下方法： 

def totalNQueens(self,n:int)>int: