第5章递归
本章思政
在算法设计中经常需要用递归方法求解，特别是后面的树和二叉树、图、查找及排序等章节中大量地用到了递归算法。递归是计算机科学中的一个重要工具，很多程序设计语言（例如C/C++）都支持递归程序设计。
本章介绍递归的定义和递归算法设计方法等，为后面的学习打下基础。
5.1
什么是递归
5.1.1递归的定义
在定义一个过程或函数时出现调用本过程或本函数的成分称为递归(recursion)。若调用自身，称为直接递归(direct recursion)。若过程或函数p调用过程或函数q，而q又调用p，称为间接递归(indirect recursion)。在算法设计中，任何间接递归算法都可以转换为直接递归算法来实现，所以后面主要讨论直接递归。
递归不仅是数学中的一个重要概念，也是计算技术中的重要概念之一。在计算技术中，与递归有关的概念有递归数列、递归过程、递归算法、递归程序和递归方法等。
(1) 递归数列指的是由递归关系所确定的数列。
(2) 递归过程指的是直接或间接调用自身的过程。
(3) 递归算法指的是包含递归过程的算法。
(4) 递归程序指的是直接或间接调用自身的程序。
(5) 递归方法指的是一种在有限步骤内根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列元素(例如数或函数)的方法。
【例5.1】根据求阶乘的定义，给出求n!（n为正整数）的递归函数。
解求n!的定义是1!=1，n!=n*(n-1)!，对应的递归函数fact(n)如下：
int fact(int n)
{if (n==1)//语句1
return 1; //语句2
else //语句3
return n*fact(n-1); //语句4
}
递归算法通常把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程中所需要的多次重复计算，大大减少了算法的代码量。
一般来说，能够用递归解决的问题应该满足以下3个条件：
(1) 需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。
(2) 递归调用的次数必须是有限的。
(3) 必须有结束递归的条件来终止递归。
递归算法的优点是结构简单、清晰，易于阅读，方便其正确性证明； 缺点是算法执行中占用的内存空间较多，执行效率低，不容易优化。
5.1.2何时使用递归
在以下3种情况下经常要用到递归方法。
1. 定义是递归的
有许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci数列等。对于这些问题的求解可以将其递归定义直接转化为对应的递归算法。例如，求n!可以转化为例5.1的递归算法。求Fibonacci数列的递归算法如下：
int Fib1(int n)//求Fibonacci数列的第n项
{if (n==1 ‖ n==2)
return(1);
else
return(Fib1(n-1)+Fib1(n-2));
}
2. 数据结构是递归的
有些数据结构是递归的。例如第2章中介绍的单链表就是一种递归数据结构，其结点类型声明如下：
typedef struct LNode
{ElemType data; //存放结点数据
struct LNode *next; //指向下一个同类型结点的指针
} LinkNode; //单链表的结点类型
其中，结构体LNode的声明用到了它自身，即指针域next是一种指向相同类型结点的指针，所以它是一种递归数据结构。
对于递归数据结构，采用递归的方法编写算法既方便又有效。例如求一个不带头结点的单链表L的所有data域(假设为int类型)之和的递归算法如下：
int Sum(LinkNode *L)
{if (L==NULL)
return 0;
else
return(Ldata+Sum(Lnext));
}
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塔座上。由此得到Hanoi1递归算法如下：
void Hanoi1(int n,char X,char Y,char Z)
{if (n==1)//只有一个盘片的情况
printf("＼t将第%d个盘片从%c移动到%c＼n",n,X,Z);
else//有两个或多个盘片的情况
{Hanoi1(n-1,X,Z,Y);
printf("＼t将第%d个盘片从%c移动到%c＼n",n,X,Z);
Hanoi1(n-1,Y,X,Z);
}
}
5.1.3递归模型
递归模型是递归算法的抽象，它反映一个递归问题的递归结构。例如，例5.1的递归算法对应的递归模型如下：
f(n)=1n=1
f(n)=n*f(n-1)n1
其中，第一个式子给出了递归的终止条件，第二个式子给出了f(n)的值与f(n-1)的值之间的关系，把第一个式子称为递归出口，把第二个式子称为递归体。
一般情况下，一个递归模型由递归出口和递归体两部分组成。递归出口(recursive exit)确定递归到何时结束，即指出明确的递归结束条件。递归体(recursive body)确定递归求解时的递推关系。
递归出口的一般格式如下：
f(s1)=m1(5.1)
这里的s1与m1均为常量，有些递归问题可能有几个递归出口。递归体的一般格式如下：
f(sn)=g(f(si)，f(si+1)，…，f(sn-1)，cj，cj+1，…，cm)(5.2)
其中，n、i、j、m均为正整数。这里的sn是一个递归“大问题”，si、si+1、…、sn-1为递归“小问题”，cj、cj+1、…、cm是若干个可以直接(用非递归方法)解决的问题，g是一个非递归函数，可以直接求值。
图5.2把大问题f(sn)转化成几个
小问题来解决
实际上，递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，如图5.2所示，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直到每个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意地分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。
为了讨论方便，设简化的递归模型(即将一个“大问题”分解为一个“小问题”)如下：
f(s1)=m1(5.3)
f(sn)=g(f(sn-1)，cn-1)(5.4)
在求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数列的Fib1算法，求Fib1(6)的过程构成的递归树如图5.4所示，向下的实箭头表示分解，向上的虚箭头表示求值，每个方框旁边的数字是该方框的求值结果，最后求得Fib1(6)为8。该递归树的高度为5，所以递归调用深度也是5。
图5.4求Fib(6)对应的递归树
5.1.4递归与数学归纳法
从递归体可以看到，如果已知si、si+1、…、sn-1，就可以确定sn。从数学归纳法的角度来看，这相当于数学归纳法的归纳步骤的内容。但仅有这个关系还不能确定这个数列，若要使它完全确定，还应给出这个数列的初始值s1。
例如，采用数学归纳法证明下式：
1+2+…+n=n(n+1)2
当n=1时，左式=1，右式=1×22=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
等式成立。即证。
数学归纳法是一种论证方法，而递归是算法和程序设计的一种实现技术，数学归纳法是递归求解问题的理论基础。可以说递归的思想来自数学归纳法。
5.2
栈 和 递 归
5.2.1函数调用栈
函数调用操作包括从一块代码到另一块代码之间的双向数据传递和执行控制转移。数据传递通过函数参数和返回值实现，另外还需要在进入函数时为函数的局部变量分配存储空间，并且在退出函数时收回这部分空间。
大多数CPU上的程序实现使用栈来支持函数调用操作。单个函数调用操作所使用的函数调用栈被称为栈帧(stack frame)结构。每次函数调用时都会相应地创建一帧，保存返回地址、函数实参和局部变量值等，并将该帧压入调用栈。若在该函数返回之前又发生了新的调用，则同样要将与新函数对应的一帧进栈，成为栈顶。函数一旦执行完毕，对应的帧便出栈，控制权交还给该函数的上层调用函数，并按照该帧中保存的返回地址确定程序中继续执行的位置。
例如，若有以下程序：
int main()
{int m,n;
…
f(m,n); //后面第一个语句的地址为d1
…
return 1;
}
void f(int s,int t)
{int i;
…
g(i);//后面第一个语句的地址为d2
…
}
void g(int d)
{int x,y;
…
}
在执行上述程序时，假设main函数的返回地址为d0。当执行main函数时，将栈帧①进栈。在main函数中调用f函数时，将栈帧②进栈。在f函数中调用g函数时，将栈帧③进栈，如图5.5所示。当g函数执行完毕，将栈帧③退栈，控制权交回到f函数，转向其中的d2地址继续执行，其余执行过程类似。
图5.5函数调用栈
5.2.2递归调用的实现
递归是函数调用的一种特殊情况，即它是调用自身代码。因此，也可以把每一次递归调用理解成调用自身代码的一个复制件。由于每次调用时它的参数和局部变量可能不相同，所以也就保证了各个复制件执行时的独立性。
但这些调用在内部实现时并不是每次调用真正去复制一个复制件存放到内存中，而是采用代码共享的方式，也就是它们都是调用同一个函数的代码，系统为每一次调用开辟一组存储单元，用来存放本次调用的返回地址以及被中断的函数的参数值。
这些单元以栈的形式存放，每调用一次进栈一次，当返回时执行出栈操作，把当前栈顶保留的值送回相应的参数中进行恢复，并按栈顶中的返回地址从断点继续执行。下面通过计算fun(5)的值介绍递归调用过程实现的内部机理。
表5.1给出了求解fun(5)的递归调用过程中程序的执行及栈的变化情况，设调用fun(5)的返回地址为d0。
在调用fun(5)时，先把返回地址d0以及参数5进栈，然后执行语句1、3、4，当遇到其中的fun(51)（即fun(4)）时，必须中断当前执行的程序，转去调用fun(4)，记录下其返回地址为d1； 在调用fun(4)时，先把返回地址d1以及参数4进栈，然后执行语句1、3、4，当遇到其中的fun(3)时转去调用fun(3)，记录下其返回地址为d2； …。直到调用fun(1)，把返回地址d4以及参数1进栈。
表5.1fun(5)的执行过程
序号调用/执行返回地址进/出栈
栈内情况
返回地址实参执行语句说明
1调用fun(5)d0进栈d051，3，42调用fun(4)d1进栈d14d051，3，4
3调用fun(3)d2进栈d23d14d051，3，4
续表
序号调用/执行返回地址进/出栈
栈内情况
返回地址实参执行语句说明
4调用fun(2)d3进栈d32d23d14d051，3，4
5调用fun(1)d4进栈d41d32d23d14d051，3，4
6执行fun(1)返回d4出栈d32d23d14d051，2求得fun(1)=1
7执行fun(2)返回d3出栈d23d14d054求得fun(2)=2
8执行fun(3)返回d2出栈d14d054求得fun(3)=6
9执行fun(4)返回d1出栈d054求得fun(4)=24
10执行fun(5)返回d0栈空4求得fun(5)=120
然后执行fun(1)，执行语句1、2，返回1并出栈一次； 执行fun(2)，执行语句4，返回2并出栈一次； …。直到执行fun(5)，此时栈空，返回120并转向d0。
例如，已知程序如下：
int S(int n)
{return (n=0) ? 0 : S(n-1)+n; }
int main()
{printf("%d＼n",S(1));
return 1;
}
程序执行时使用一个栈来保存调用过程的信息，这些信息用main()、S(0)和S(1)表示，那么自栈底到栈顶保存的信息的顺序是怎样的？
首先从main()开始执行程序，将main()信息进栈，遇到调用S(1)，将S(1)信息进栈，在执行递归函数S(1)时又遇到调用S(0)，再将S(0)信息进栈。所以，自栈底到栈顶保存的信息的顺序是main()→S(1)→S(0)。
5.2.3递归算法的时空性能分析
1. 递归算法的时间复杂度分析
递归算法分析不能简单地采用非递归算法分析的方法，递归算法分析属于变长时空分析，非递归算法分析属于定长时空分析。
在递归算法分析中，首先写出对应的递推式，然后求解递推式得出算法的执行时间或者空间。例如，对于前面求Hanoi问题的递归算法，分析其时间复杂度的过程如下。
设Hanoi1(n，x，y，z)的执行时间为T(n)，则两个问题规模为n-1的子问题的执行时间均为T(n-1)，总时间是累加关系。对应的递推式如下：
T(n)=1当n=1时
T(n)=2T(n-1)+1 当n1时
则： 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)
【例5.2】有如下递归算法：
void fun(int a［］，int n，int k)//数组a共有n个元素，执行时间为T1(n，k)
{int i;
if (k==n-1)
{for (i=0;in;i++)
printf("%d＼n"，a［i］); //该语句的执行次数为n
}
else
{for (i=k;in;i++)
a［i］=a［i］+i*i; //该语句的执行次数为n-k
fun(a，n，k+1); //执行时间为T1(n，k+1)
}
}
调用上述算法的语句为fun(a，n，0)，求其时间复杂度。
解设fun(a，n，k)的执行时间为T1(n，k)，fun(a，n，0)的执行时间为T(n)。显然有T(n)=T1(n，0)。由fun()算法得到如下执行时间的递推式：
T1(n，k)=n当k=n-1时
(n-k)+T1(n，k+1)其他情况
则： T(n)=T1(n，0)=n+T1(n，1)
=n+(n-1)+T1(n，2)
︙
=n+(n-1)+…+2+T1(n，n-1)
=(n+2)(n－1)2+n=n22+3n2－1
=O(n2)
所以调用fun(a，n，0)的时间复杂度为O(n2)。
2. 递归算法的空间复杂度分析
递归算法执行中使用了系统栈空间，因此需要根据递归调用的深度来分析递归算法的空间复杂度，其过程与递归算法的时间复杂度分析类似。例如，对于前面求Hanoi问题的递归算法，分析其空间复杂度的过程如下。
设Hanoi1(n，x，y，z)的临时空间为S(n)，则两个问题规模为n-1的子问题的临时空间均为S(n-1)，总空间是最大值关系，因为前一个子问题执行完毕其空间被释放，释放的空间被后一个子问题重复使用。对应的递推式如下：
S(n)=1当n=1时
S(n)=S(n-1)+1当n1时
则： S(n)=S(n-1)+1=(S(n-2)+1)+1
=…
=S(1)+1+…+1
=1+1+…+1n个1=O(n)
【例5.3】对于例5.2的递归算法，分析调用语句fun(a，n，0)的空间复杂度。
解设fun(a，n，k)占用的临时空间为S1(n，k)，fun(a，n，0)占用的临时空间为S(n)。显然有S(n)=S1(n，0)。由fun()算法得到如下占用临时空间的递推式：
S1(n，k)=1当k=n-1时（此时仅定义了一个临时变量i）
1+S1(n，k+1)其他情况
则： S(n)=S1(n，0)=1+S1(n，1)
=1+1+S1(n，2)
︙
=1+1+…+1+S1(n，n-1)
=1+1+…+1n个1=O(n)
所以调用fun(a，n，0)的空间复杂度为O(n)。
5.2.4递归到非递归的转换*
通常递归算法的执行效率比较差，当递归调用层次较深时容易出现“栈溢出”，可以将递归算法转换为等效的非递归算法，主要有两种方法，即直接转换法和间接转换法。
1. 直接转换法
所谓直接转换法就是用迭代方式或者循环语言替代多次重复的递归调用。直接转换法通常用来消除尾递归和单向递归。
如果一个递归函数中的递归调用语句是最后一条执行语句，且把当前运算结果放在参数里传给下层函数，称这种递归调用为尾递归（tail recursion）。例如，例5.1的递归函数转换为尾递归函数如下：
int fact1(int n,int ans)//求n!的尾递归算法
{if(n==1)
return ans;
else
return fact1(n-1,n*ans);
}
利用上述算法求5!的过程是，fact1(5，1)→fact1(4，5)→fact1(3，20)→fact1(2，60) →fact1(1，120)，最后返回值120表示5!=120。
有些编译器针对尾递归的特点通过优化将返回地址不保存在系统栈中，从而节省栈空间开销。
单向递归是指递归的求值过程总是朝着一个方向进行的，例如，前面求Fibonacci数列的递归算法Fib1就属于单向递归，因为求值过程是1，1，2，3，5，8，…，即单向生长的。可以采用迭代方式将Fib1转换为如下非递归算法：
int Fib2(int n)//求Fibonacci数列的第n项
{int a=1,b=1,i,s;
if (n==1 ‖ n==2)
return 1;
else
{for (i=3;i=n;i++)
{s=a+b;
a=b;
b=s;
}
return s;
}
}
2. 间接转换法
其他相对复杂的递归算法不能直接求值，在执行中需要回溯。可以在理解递归调用实现过程的基础上用栈来模拟递归执行过程，即使用栈保存中间结果，从而将其转换为等效的非递归算法，这称为间接转换法。
例如，在将前面求解Hanoi问题的递归算法Hanoi1转换为等价的非递归算法时，需要使用一个栈暂时存放还不能直接移动盘片的任务/子任务。
首先将任务Hanoi(n，x，y，z)进栈，栈不空时循环： 出栈一个任务Hanoi(n，x，y，z)，如果它是可直接移动的，就移动盘片； 否则该任务转化为Hanoi(n-1，x，z，y)、move(n，x，z)、Hanoi(n-1，y，x，z)，按相反顺序(即将3个任务Hanoi(n-1，y，x，z)、move(n，x，z)和Hanoi(n-1，x，z，y))依次进栈，其中move(n，x，z)是可直接移动的任务。为此设计一个顺序栈的类型如下：
typedef struct
{int n; //盘片的个数
char x,y,z; //3个塔座
bool flag; //可直接移动盘片时为true,否则为false
}ElemType; //顺序栈中元素的类型
typedef struct
{ElemType data［MaxSize］; //存放元素
int top; //栈顶指针
}StackType; //顺序栈的类型
栈中的每个元素对应一个求解任务，flag标识该任务是否可以直接移动盘片。采用第3章的原理设计好顺序栈的基本运算算法(除了将SqStack改为StackType以外，其他代码都是相同的)。对应的求解Hanoi问题的非递归算法如下：
void Hanoi2(int n, char x, char y, char z)
{StackType *st; //定义顺序栈指针
ElemType e,e1,e2,e3;
if (n=0) return; //参数错误时直接返回
InitStack(st); //初始化栈
e. n=n; e.x=x; e.y=y; e.z=z; e.flag=false;
Push(st,e); //元素e进栈
while (!StackEmpty(st))//栈不空时循环
{Pop(st,e); //出栈元素e
if (e.flag==false)//当不能直接移动盘片时
{e1.n=e.n-1; e1.x=e.y; e1.y=e.x; e1.z=e.z;
if (e1.n==1)//只有一个盘片时可直接移动
e1.flag=true;
else//有一个以上盘片时不能直接移动
e1.flag=false;
Push(st,e1); //处理Hanoi(n-1,y,x,z)步骤
e2.n=e.n; e2.x=e.x; e2.y=e.y; e2.z=e.z; e2.flag=true;
Push(st,e2); //处理move(n,x,z)步骤
e3.n=e.n-1; e3.x=e.x; e3.y=e.z; e3.z=e.y;
if (e3.n==1)//只有一个盘片时可直接移动
e3.flag=true;
else
e3.flag=false; //有一个以上盘片时不能直接移动
Push(st,e3); //处理Hanoi(n-1,x,z,y)步骤
}
else//当可以直接移动时
printf("＼t将第%d个盘片从%c移动到%c＼n",e.n,e.x,e.z);
}
DestroyStack(st); //销毁栈
}
5.3
递归算法的设计
5.3.1递归算法的设计步骤
递归算法设计的基本步骤是先确定求解问题的递归模型，再转换成对应的C/C++语言函数。由于递归模型反映递归问题的“本质”，所以前一步是关键，也是讨论的重点。
递归算法的求解过程是先将整个问题划分为若干个子问题，然后分别求解子问题，最后获得整个问题的解。这是一种分而治之的思路，通常由整个问题划分的若干子问题的求解是独立的，所以求解过程对应一棵递归树。如果在设计算法时就考虑递归树中的每一个分解/求值部分会使问题复杂化，不妨只考虑递归树中第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.4】采用递归算法求实数数组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时
MIN(f(A，i-1)，A［i］)其他情况
由此得到以下递归求解算法：
double Min(double A［］,int i)
{double min;
if (i==0) return A［0］;
else
{min=Min(A,i-1);
if (minA［i］) return(A［i］);
else return(min);
}
}
例如，若一个实数数组为double a［］={9.2，5.5，3.8，7.1，6.5}，调用Min(a，4)返回最小元素3.8。
【例5.5】求含n（n>1）个元素的顺序表L中的最大元素。
解法1： 顺序表L采用数组data［0..n-1］存放全部元素，采用与例5.4类似的思路。对应的递归算法如下：
ElemType Max1(SqList L,int i)//解法1：求顺序表L中的最大元素
{ElemType max;
if (i==0) return L.data［0］;
else
{max=Max1(L,i-1);
if (maxL.data［i］) return L.data［i］;
else return max;
}
}
解法2： 假设顺序表L中data数组的元素为a0、a1、…、an-1，将其分解成（a0，a1，…，am）和（am+1，…，an-1）左、右两个子表，分别求得它们的最大元素为max1和max2，则整个顺序表L的最大元素就是max1和max2中的较大者，而左、右子表求最大元素是两个相似的子问题。对应的递归算法如下：
ElemType Max2(SqList L,int i,int j)//解法2：求顺序表L中的最大元素
{int mid;
ElemType max,max1,max2;
if (i==j) //顺序表中只有一个元素，即递归出口
max=L.data［i］; //该元素就是最大元素
else //顺序表中有多个元素
{mid=(i+j)/2; //求中间位置
max1=Max2(L,i,mid); //递归调用求左子表的最大元素max1
max2=Max2(L,mid+1,j); //递归调用求右子表的最大元素max2
max=(max1max2)?max1:max2; //求整个表的最大元素max
}
return(max);
}
5.3.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)。
对于不带头结点的单链表，其结点类型为LinkNode，每个结点的next域为LinkNode类型的指针，这样的单链表通过首结点指针来标识。采用递归数据结构的定义如下：
SL=(D，Op)
其中，D是由部分或全部结点构成的单链表的集合(含空单链表)，Op={op1}，op1的定义如下：
op1(L)=Lnext//L为含一个或一个以上结点的单链表
显然这个递归运算符是一元运算符，且具有封闭性。也就是说，若L为不带头结点的非空单链表，则L->next也是一个不带头结点的单链表。
实际上，递归算法设计步骤中的第2步是用于确定递归模型中的递归体。在假设原问题f(s)合理的小问题f(s′)时，需要考虑递归数据结构的递归运算。例如，在设计不带头结点的单链表的递归算法时，通常设s为以L为首结点指针的整个单链表，s′为除首结点以外余下结点构成的单链表(由L->next标识，而该运算为递归运算)。
【例5.6】假设有一个不带头结点的单链表L，设计一个算法释放其中的所有结点。
解设f(L)的功能是释放a1~an的所有结点，则f(L->next)的功能是释放a2~an的所有结点，如图5.6所示。假设f(L->next)是可实现的，则f(L)的功能是先调用f(L->next)，然后释放L所指的结点。
图5.6一个不带头结点的单链表
对应的递归模型如下：
f(L) ≡ 不做任何事情当L=NULL时
f(L) ≡ f(L->next)； 释放L所指的结点其他情况
其中，“≡”表示功能等价关系。对应的算法如下：
void release(LinkNode *&L)
{if (L!=NULL)
{release(Lnext);
free(L);
}
}
说明： 在对单链表设计递归算法时通常采用不带头结点的单链表。以图5.6为例，L->next表示的单链表一定是不带头结点的，也就是说“小问题”的单链表是不带头结点的单链表，这样“大问题”(即整个单链表)也应设计成不带头结点的单链表。
所以在设计递归算法时，如果处理的数据是递归数据结构，需要对该数据结构及其递归运算进行分析，从而设计出正确的递归体。再假设一种特殊情况，得到递归出口。
5.3.3基于递归求解方法的递归算法设计
当求解问题的方法是递归(例如Hanoi问题)的或者可以转换成递归方法求解时(例如皇后问题)，可以设计成递归算法。
例如，求f(n)=1+2+…+n(n≥1)，这个问题可以转化为用递归方法求解，假设“小问题”是f(n-1)=1+2+…+(n-1)，它是可求的，则f(n)=f(n-1)+n。
对于采用递归方法求解的问题，需要对问题本身进行分析，确定大、小问题解之间的关系，构造合理的递归体。
【例5.7】采用递归算法求解迷宫问题，并输出从入口到出口的所有迷宫路径。
解迷宫问题在第3章中介绍过，设mgpath(int xi，int yi，int xe，int ye，PathType path)是求从(xi，yi)到(xe，ye)的迷宫路径，用path变量保存一条迷宫路径，其中PathType类型的声明如下。
typedef struct
{int i; //方块的行号
int j; //方块的列号
}Box; //方块的类型
typedef struct
{Box data［MaxSize］; //存放一条路径上的所有方块
int length; //迷宫路径的长度
}PathType; //迷宫路径的类型
当从(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)是“小问题”(即大问题=试探一步+小问题)。求解上述迷宫问题的递归模型如下：
mgpath(xi,yi,xe,ye,path) ≡ 将(xi,yi)添加到path中;输出path中的迷宫路径;
若(xi,yi)=(xe,ye)为出口
mgpath(xi,yi,xe,ye,path) ≡ 对于(xi,yi)四周的每一个相邻方块(i,j)： 若(xi,yi)不是出口且可走
① 将(xi,yi)添加到path中;
② mg［xi］［yi］=-1;
③ mgpath(i,j,xe,ye,path);
④ path回退一步并置mg［xi］［yi］=0;
mgpath(xi,yi,xe,ye,path) ≡ 不做任何事情; 若(xi,yi)不是出口且不可走
在上述递归模型中，当完成“小问题”mgpath(i，j，xe，ye，path)后将path回退并置mg［xi］［yi］为0(对应④)，其目的是恢复前面求迷宫路径而改变的环境，以便找出所有的迷宫路径。对应的递归算法如下：
void mgpath(int xi,int yi,int xe,int ye,PathType path)
//求解迷宫路径为(xi,yi)(xe,ye)
{int di,k,i,j;
if (xi==xe && yi==ye)//找到了出口,输出一个迷宫路径
{path.data［path.length］.i=xi; //将(xi,yi)添加到path中
path.data［path.length］.j=yi;
path.length++;
printf("迷宫路径%d如下:＼n",++count); //输出path中的迷宫路径
for (k=0;kpath.length;k++)
printf("＼t(%d,%d)",path.data［k］.i,path.data［k］.j);
printf("＼n");
}
else//(xi,yi)不是出口
{if (mg［xi］［yi］==0)//(xi,yi)是一个可走方块
{di=0;
while (di4)//处理(xi,yi)四周的每一个相邻方块(i,j)
{path.data［path.length］.i=xi; //①将(xi,yi)添加到path中
path.data［path.length］.j=yi;
path.length++; //路径长度增1
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;
}
mg［xi］［yi］=-1; //②mg［xi］［yi］=-1
mgpath(i,j,xe,ye,path); //③mgpath(i,j,xe,ye,path)
mg［xi］［yi］=0; //④恢复(xi,yi)为可走
path.length--; //回退一个方块
di++; //继续处理(xi,yi)下一个相邻方块
}
}
}
}
本算法输出所有的迷宫路径，对于如图5.7(a)所示的迷宫，指定入口为(1,1)、出口为(4，4)，求出的迷宫路径有4条，如图5.7(b)所示，可以通过比较路径长度求出最短迷宫路径(可能存在多条最短迷宫路径)。
图5.7一个迷宫及其所有的迷宫路径
本 章 小 结
本章的基本学习要点如下：
(1) 理解递归的定义和递归模型。
(2) 理解递归算法的执行过程。
(3) 掌握递归算法设计的一般方法。
(4) 灵活地运用递归算法解决一些较复杂的应用问题。
练习题5
1. 有以下递归函数：
void fun(int n)
{if (n==1)
printf("a:%d＼n",n);
else
{printf("b:%d＼n",n);
fun(n-1);
printf("c:%d＼n",n);
}
}
分析调用fun(5)的输出结果。
2. 有以下递归算法用于对数组a［i..j］中的元素进行归并排序：
void mergesort(int a［］，int i，int j)
{int m;
if (i!=j)
{m=(i+j)/2;
mergesort(a，i，m);
mergesort(a，m+1，j);
merge(a，i，j，m);
}
}
求执行mergesort(a，0，n-1)的时间复杂度。其中，merge(a，i，j，m)用于两个有序子序列a［i..m］和a［m+1..j］的合并，是非递归函数，它的时间复杂度为O(合并的元素个数)。
3. 已知A［0..n-1］为实数数组，设计一个递归算法求这n个元素的平均值。
4. 设计一个算法求正整数n的位数。
5. 上楼可以一步上一阶，也可以一步上两阶，设计一个递归算法，计算共有多少种不同的走法。
6. 设计一个递归算法，利用顺序串的基本运算求串s的逆串。
7. 设有一个不带表头结点的单链表L，设计一个递归算法count(L)求以L为首结点指针的单链表的结点个数。
8. 设有一个不带表头结点的单链表L，设计两个递归算法，traverse(L)正向输出单链表L中的所有结点值，traverseR(L)反向输出单链表L中的所有结点值。
9. 设有一个不带表头结点的单链表L，设计两个递归算法，del(L，x)删除单链表L中第一个值为x的结点，delall(L，x)删除单链表L中所有值为x的结点。
10. 设有一个不带表头结点的单链表L，设计两个递归算法，maxnode(L)返回单链表L中的最大结点值，minnode(L)返回单链表L中的最小结点值。
11. 设计一个模式匹配算法，其中模式串t中含一个或多个通配符'*'，每个'*'可以和任意子串匹配。对于目标串s，求其中匹配模式串t的一个子串的位置（'*'不能出现在t的开头）。
上机实验题5
验证性实验
实验题1： 采用递归和非递归方法求解Hanoi问题
目的： 领会基本递归算法的设计和递归到非递归的转换方法。
内容： 编写程序exp51.cpp，采用递归和非递归方法求解Hanoi问题，输出3个盘片的移动过程。
实验题2： 求路径和路径条数问题
目的： 领会基本递归算法的设计和递归的执行过程。
内容： 编写程序exp52.cpp求路径和路径条数。有一个m×n的网格，如图5.8所示为一个2×5的网格。现在一个机器人位于左上角，该机器人
图5.8一个2×5的网格
在任何位置上时只能向下或者向右移动一步，问机器人到达网格的右下角(1，1)位置的
所有可能的路径条数，并输出所有的路径。以m=2，n=2为例说明输出所有路径的过程。
设计性实验
实验题3： 恢复IP地址
目的： 掌握基本递归算法的设计。
内容： 编写程序exp53.cpp恢复IP地址。给定一个仅包含数字的字符串，恢复它的所有可能的有效IP地址。例如，给定字符串为"25525511135"，返回"255.255.11.135"和"255.255.111.35"(顺序可以任意)。
实验题4： 高效求解xn
目的： 掌握基本递归算法的设计。
内容： 编写程序exp54.cpp高效求解xn，要求最多使用O(log2n)次递归调用。
实验题5： 用递归方法逆置带头结点的单链表
目的： 掌握单链表递归算法的设计方法。
内容： 编写一个程序exp55.cpp，用递归方法逆置一个带头结点的单链表。
实验题6： 用递归方法求单链表中的倒数第k个结点
目的： 掌握单链表递归算法的设计方法。
内容： 编写一个程序exp56.cpp，用递归方法求单链表中的倒数第k个结点。
综合性实验
实验题7： 用递归方法求解n皇后问题
目的： 深入掌握递归算法的设计方法。
内容： 编写一个程序exp57.cpp，用递归方法求解n皇后问题，对n皇后问题的描述参见第3章中的实验题8。
实验题8： 用递归方法求解0/1背包问题
目的： 深入掌握递归算法的设计方法。
内容： 编写一个程序exp58.cpp，用递归方法求解0/1背包问题。0/1背包问题是设有n件物品，每件物品有相应的重量和价值，求从这n件物品中选取全部或部分物品的方案，使选中物品的总重量不超过指定的限制重量W，但选中物品的价值之和为最大。注意，每种物品要么被选中，要么不被选中。
LeetCode在线编程题5
1. LeetCode509——斐波那契数★
2. LeetCode50——Pow(x,n)★★
3. LeetCode206——翻转链表★
4. LeetCode234——回文链表★
5. LeetCode24——两两交换链表中的结点★★
6. LeetCode59——螺旋矩阵Ⅱ★★
7. LeetCode51——n皇后★★★