第 6章 递归
6.3 递归算法到非递归算法的转换
6.1 什么是递归
6.2 递归算法的设计本章小结
6.1 什么是递归
6.1.1 递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分，称之为 递归 。若调用自身，称之为 直接递归 。若过程或函数 p调用过程或函数 q，
而 q又调用 p，称之为 间接递归 。
如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为 尾递归 。
例 6.1 以下是求 n!（ n为正整数 ） 的递归函数 。
int fun(int n)
{ int x;
if (n==1) /*语句 1*/
x=1; /*语句 2*/
else /*语句 3*/
x=fun(n-1)*n; /*语句 4*/
return(x); /*语句 5*/
}
在该函数 fun(n)求解过程中,直接调用 fun(n-1)（ 语句 4） 自身,所以它是一个直接递归函数 。 又由于递归调用是最后一条语句,所以它又属于尾递归 。
6.1.2 何时使用递归在以下三种情况下,常常要用到递归的方法 。
1,定义是递归的有许多数学公式、数列等的定义是递归的。例如，
求 n!和 Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。
2,数据结构是递归的有些数据结构是递归的。例如，第 2章中介绍过的单链表就是一种递归数据结构，其结点类型定义如下：
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LinkList;
该定义中，结构体 LNode的定义中用到了它自身，
即指针域 next是一种指向自身类型的指针，所以它是一种递归数据结构。
对于递归数据结构,采用递归的方法编写算法既方便又有效 。 例如,求一个不带头结点的单链表 head的所有 data域 （ 假设为 int型 ） 之和的递归算法如下：
int Sum(LinkList *head)
{
if (head==NULL)
return 0;
else
return(head->data+Sum(head->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,x,y,z)
Hanoi(n-1,x,z,y)；
move(n,x,z):将第 n个圆盘从 x移到 z；
Hanoi(n-1,y,x,z)
6.1.3 递归模型递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：
fun(1)=1 (1)
fun(n)=n*fun(n-1) n>1 (2)
其中,第一个式子给出了递归的终止条件,第二个式子给出了 fun(n)的值与 fun(n-1)的值之间的关系,我们把第一个式子称为 递归出口,把第二个式子称为 递归体 。
一般地，一个递归模型是由递归出口和递归体两部分组成，前者确定递归到何时结束，后者确定递归求解时的递推关系。递归出口的一般格式如下：
f(s1)=m1 (6.1)
这里的 s1与 m1均为常量,有些递归问题可能有几个递归出口 。 递归体的一般格式如下：
f(sn+1)=g(f(si),f(si+1),…,f(sn),cj,cj+1,…,cm) (6.2)
其中,n,i,j,m均为正整数 。 这里的 sn+1是一个递归,大问题,,si,si+1,…,sn为递归,小问题,,cj，
cj+1,…,cm是若干个可以直接 （ 用非递归方法 ） 解决的问题,g是一个非递归函数,可以直接求值 。
实际上，递归思路是把一个不能或不好直接求解的
“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决（此时分解到递归出口）。但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，
即求解过程与环境都相似。
为了讨论方便，简化上述递归模型为：
f(s1)=m1 (6.3)
f(sn)=g(f(sn-1),c) (6.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)便计算出来了，因此，递归的执行过程由分解和求值两部分构成。
f u n (5 )
d 1,f u n (4 )
d 2,f u n (3 )
d 3,f u n (2 )
d 4,f u n (1 )
返回 1
f u n (2 )= 2
f u n (3 )= 6
f u n (4 )= 2 4
f u n (5 )= 1 2 0
求解 fun(5)的过程如下：
6.2 递归算法的设计递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解 。 而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,
分别求解,如此反复进行,直到不能再划分成子问题,
或已经可以求解为止 。 这种自上而下将问题分解,求解,再自上而下引用,合并,求出最后解答的过程称为递归求解过程 。 这是一种分而治之的算法设计方法 。
递归算法设计先要给出递归模型,再转换成对应的
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时等式成立相似）。
例如,采用递归算法求实数数组 A[0..n-1]中的最小值 。
假设 f(A,i)函数求数组元素 A[0]～ A[i]中的最小值 。 当 i=0时,有
f(A,i)=A[0]；假设 f(A,i-1)已求出,则 f(A,i)=MIN(f(A,i-1),A[i]),其中 MIN()为求两个值较小值函数 。 因此得到如下递归模型：
A[0] 当 i=0时
f(A,i)=
MIN(f(A,i-1),A[i]) 其他情况由此得到如下递归求解算法：
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;
}
}
6.3 递归算法到非递归算法的转换递归算法有两个基本特性：一是递归算法是一种分而治之的,把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的；二是递归算法的时间效率通常比较差 。
因此,对求解某些问题时,我们希望用递归算法分析问题,用非递归算法具体求解问题 。 这就需要把递归算法转换为非递归算法 。
把递归算法转化为非递归算法有如下三种基本方法：
（ 1） 对于尾递归和单向递归的算法,可用循环结构的算法替代 。
（ 2） 自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递归算法替代递归算法 。
（ 3） 利用栈保存参数,由于栈的后进先出特性吻合递归算法的执行过程,因而可以用非递归算法替代递归算法 。
本节讨论第（ 1）种和第（ 2）种情况的递归算法转化为非递归算法的问题，前者是一种是直接转化法，不需要使用栈，后者是间接转化法，需要使用栈。第（ 3）
种情况也需要使用栈，但因具体情况而异，例如，在第
7章的例 7.6就是这种情况的一个例子。
6.3.1 尾递归和单向递归的消除采用循环结构消除尾递归和单向递归 。 求解 Fibonacci数列的算法如下：
int Fib(int n)
{ int i,f1,f2,f3;
if (n==1 || n==2) return(n);
f1=1;f2=2;
for (i=3;i<=n;i++)
{ f3=f1+f2;
f1=f2;f2=f3;
}
return(f3);
}
采用循环结构消除递归没有通用的转换算法,对于具体问题要深入分析对应的递归结构,设计有效的循环语句进行递归到非递归的转换 。
6.3.2 模拟系统的运行时栈消除递归对于不属于尾递归和单向递归的递归算法,很难转化为与之等价的循环算法 。 但所有的递归程序都可以转化为与之等价的非递归程序 （ 例如,C/C++语言就是先将递归程序转化为非递归程序,然后求解的 ）,
有一个通用的算法可以将递归程序转化为非递归程序
（ 详见参考文献 [2]8.4节 ）,由于这个算法过于通用,
比较复杂,不易理解,而且通常需要使用 goto转移语句,违反结构化程序设计规定,因此,在这里不作介绍 。
下面讨论直接使用栈保存中间结果,从而将递归算法转化为非递归算法的过程 。
仍以例 6.1的递归算法进行讨论,其递归模型有一个递归出口和一个递归体两个式子,分别称为 （ 1） 式和 （ 2） 式 。 设计一个栈,其结构如下：
struct
{ int vn; /*保存 n值 */
int vf; /*保存 fun1(n)值 */
int tag; /*标识是否求出 fun1(n)值,1:未求出,0:已求出 */
} St[MaxSize]; /*定义栈 */
计算 fun1(5)之值的过程如下：
将 (5,*,1)进栈 ;
while (栈不空 )
{ if (栈顶元素未计算出栈顶元素的 vf值即 St[top].tag==1)
{ if (栈顶元素满足 (1)式 )
求出对应的 St[top].vf值,并置 St[top].tag=0;
表示已求出对应的函数值 ;
else /*栈顶元素满足 (2)式 */
将 (St[top].vn-1,*,1)进栈 ;
}
else if (栈顶元素已计算出栈顶元素的 vf值即 St[top].tag==0)
显然栈顶元素由次栈顶元素通过 (2)式分解得到的,回过来由栈顶元素的 vf值计算出次栈顶元素的 vf值并退栈 ;
if (栈中只有一个已求出 vf值的元素 )
退出循环 ;
}
St[0].vf即为所求的 fun1(n)值 ;
求 fun1(5)时栈 St中元素的变化见教材 p125图 6.2所示 。对应的非递归 fun1算法如下：
int fun1(int n)
{ top++; /*初值进栈 */
St[top].vn=n; St[top].tag=1;
while (top>-1) /*栈不空时循环 */
{ if (St[top].tag==1) /*未计算出栈顶元素的 vf值 */
{ if (St[top].vn==1) /*(1)式 */
{ St[top].vf=1;
St[top].tag=0;
}
else /*(2)式 */
{ top++;
St[top].vn=St[top-1].vn-1; St[top].tag=1;
}
}
else if (St[top].tag==0) /*已计算出 vf值 */
{ St[top-1].vf=St[top-1].vn*St[top].vf; /*(2)式 */
St[top-1].tag=0;
top--;
}
if (top==0 && St[top].tag==0)
/*栈中只有一个已求出 vf的元素时退出循环 */
break;
}
return(St[top].vf);
}
本章小结本章基本学习要点如下：
（ 1） 理解递归的定义和递归模型 。
（ 2） 重点掌握递归的执行过程 。
（ 3） 掌握递归设计的一般方法 。
（ 4） 掌握消除递归的基本方法 。
（ 5）灵活运用递归算法解决一些较复杂应用问题。
练习教材中 p129的习题 1和 2。
6.3 递归算法到非递归算法的转换
6.1 什么是递归
6.2 递归算法的设计本章小结
6.1 什么是递归
6.1.1 递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分，称之为 递归 。若调用自身，称之为 直接递归 。若过程或函数 p调用过程或函数 q，
而 q又调用 p，称之为 间接递归 。
如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为 尾递归 。
例 6.1 以下是求 n!（ n为正整数 ） 的递归函数 。
int fun(int n)
{ int x;
if (n==1) /*语句 1*/
x=1; /*语句 2*/
else /*语句 3*/
x=fun(n-1)*n; /*语句 4*/
return(x); /*语句 5*/
}
在该函数 fun(n)求解过程中,直接调用 fun(n-1)（ 语句 4） 自身,所以它是一个直接递归函数 。 又由于递归调用是最后一条语句,所以它又属于尾递归 。
6.1.2 何时使用递归在以下三种情况下,常常要用到递归的方法 。
1,定义是递归的有许多数学公式、数列等的定义是递归的。例如，
求 n!和 Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。
2,数据结构是递归的有些数据结构是递归的。例如，第 2章中介绍过的单链表就是一种递归数据结构，其结点类型定义如下：
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LinkList;
该定义中，结构体 LNode的定义中用到了它自身，
即指针域 next是一种指向自身类型的指针，所以它是一种递归数据结构。
对于递归数据结构,采用递归的方法编写算法既方便又有效 。 例如,求一个不带头结点的单链表 head的所有 data域 （ 假设为 int型 ） 之和的递归算法如下：
int Sum(LinkList *head)
{
if (head==NULL)
return 0;
else
return(head->data+Sum(head->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,x,y,z)
Hanoi(n-1,x,z,y)；
move(n,x,z):将第 n个圆盘从 x移到 z；
Hanoi(n-1,y,x,z)
6.1.3 递归模型递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：
fun(1)=1 (1)
fun(n)=n*fun(n-1) n>1 (2)
其中,第一个式子给出了递归的终止条件,第二个式子给出了 fun(n)的值与 fun(n-1)的值之间的关系,我们把第一个式子称为 递归出口,把第二个式子称为 递归体 。
一般地，一个递归模型是由递归出口和递归体两部分组成，前者确定递归到何时结束，后者确定递归求解时的递推关系。递归出口的一般格式如下：
f(s1)=m1 (6.1)
这里的 s1与 m1均为常量,有些递归问题可能有几个递归出口 。 递归体的一般格式如下：
f(sn+1)=g(f(si),f(si+1),…,f(sn),cj,cj+1,…,cm) (6.2)
其中,n,i,j,m均为正整数 。 这里的 sn+1是一个递归,大问题,,si,si+1,…,sn为递归,小问题,,cj，
cj+1,…,cm是若干个可以直接 （ 用非递归方法 ） 解决的问题,g是一个非递归函数,可以直接求值 。
实际上，递归思路是把一个不能或不好直接求解的
“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决（此时分解到递归出口）。但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，
即求解过程与环境都相似。
为了讨论方便，简化上述递归模型为：
f(s1)=m1 (6.3)
f(sn)=g(f(sn-1),c) (6.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)便计算出来了，因此，递归的执行过程由分解和求值两部分构成。
f u n (5 )
d 1,f u n (4 )
d 2,f u n (3 )
d 3,f u n (2 )
d 4,f u n (1 )
返回 1
f u n (2 )= 2
f u n (3 )= 6
f u n (4 )= 2 4
f u n (5 )= 1 2 0
求解 fun(5)的过程如下：
6.2 递归算法的设计递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解 。 而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,
分别求解,如此反复进行,直到不能再划分成子问题,
或已经可以求解为止 。 这种自上而下将问题分解,求解,再自上而下引用,合并,求出最后解答的过程称为递归求解过程 。 这是一种分而治之的算法设计方法 。
递归算法设计先要给出递归模型,再转换成对应的
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时等式成立相似）。
例如,采用递归算法求实数数组 A[0..n-1]中的最小值 。
假设 f(A,i)函数求数组元素 A[0]～ A[i]中的最小值 。 当 i=0时,有
f(A,i)=A[0]；假设 f(A,i-1)已求出,则 f(A,i)=MIN(f(A,i-1),A[i]),其中 MIN()为求两个值较小值函数 。 因此得到如下递归模型：
A[0] 当 i=0时
f(A,i)=
MIN(f(A,i-1),A[i]) 其他情况由此得到如下递归求解算法：
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;
}
}
6.3 递归算法到非递归算法的转换递归算法有两个基本特性：一是递归算法是一种分而治之的,把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的；二是递归算法的时间效率通常比较差 。
因此,对求解某些问题时,我们希望用递归算法分析问题,用非递归算法具体求解问题 。 这就需要把递归算法转换为非递归算法 。
把递归算法转化为非递归算法有如下三种基本方法：
（ 1） 对于尾递归和单向递归的算法,可用循环结构的算法替代 。
（ 2） 自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递归算法替代递归算法 。
（ 3） 利用栈保存参数,由于栈的后进先出特性吻合递归算法的执行过程,因而可以用非递归算法替代递归算法 。
本节讨论第（ 1）种和第（ 2）种情况的递归算法转化为非递归算法的问题，前者是一种是直接转化法，不需要使用栈，后者是间接转化法，需要使用栈。第（ 3）
种情况也需要使用栈，但因具体情况而异，例如，在第
7章的例 7.6就是这种情况的一个例子。
6.3.1 尾递归和单向递归的消除采用循环结构消除尾递归和单向递归 。 求解 Fibonacci数列的算法如下：
int Fib(int n)
{ int i,f1,f2,f3;
if (n==1 || n==2) return(n);
f1=1;f2=2;
for (i=3;i<=n;i++)
{ f3=f1+f2;
f1=f2;f2=f3;
}
return(f3);
}
采用循环结构消除递归没有通用的转换算法,对于具体问题要深入分析对应的递归结构,设计有效的循环语句进行递归到非递归的转换 。
6.3.2 模拟系统的运行时栈消除递归对于不属于尾递归和单向递归的递归算法,很难转化为与之等价的循环算法 。 但所有的递归程序都可以转化为与之等价的非递归程序 （ 例如,C/C++语言就是先将递归程序转化为非递归程序,然后求解的 ）,
有一个通用的算法可以将递归程序转化为非递归程序
（ 详见参考文献 [2]8.4节 ）,由于这个算法过于通用,
比较复杂,不易理解,而且通常需要使用 goto转移语句,违反结构化程序设计规定,因此,在这里不作介绍 。
下面讨论直接使用栈保存中间结果,从而将递归算法转化为非递归算法的过程 。
仍以例 6.1的递归算法进行讨论,其递归模型有一个递归出口和一个递归体两个式子,分别称为 （ 1） 式和 （ 2） 式 。 设计一个栈,其结构如下：
struct
{ int vn; /*保存 n值 */
int vf; /*保存 fun1(n)值 */
int tag; /*标识是否求出 fun1(n)值,1:未求出,0:已求出 */
} St[MaxSize]; /*定义栈 */
计算 fun1(5)之值的过程如下：
将 (5,*,1)进栈 ;
while (栈不空 )
{ if (栈顶元素未计算出栈顶元素的 vf值即 St[top].tag==1)
{ if (栈顶元素满足 (1)式 )
求出对应的 St[top].vf值,并置 St[top].tag=0;
表示已求出对应的函数值 ;
else /*栈顶元素满足 (2)式 */
将 (St[top].vn-1,*,1)进栈 ;
}
else if (栈顶元素已计算出栈顶元素的 vf值即 St[top].tag==0)
显然栈顶元素由次栈顶元素通过 (2)式分解得到的,回过来由栈顶元素的 vf值计算出次栈顶元素的 vf值并退栈 ;
if (栈中只有一个已求出 vf值的元素 )
退出循环 ;
}
St[0].vf即为所求的 fun1(n)值 ;
求 fun1(5)时栈 St中元素的变化见教材 p125图 6.2所示 。对应的非递归 fun1算法如下：
int fun1(int n)
{ top++; /*初值进栈 */
St[top].vn=n; St[top].tag=1;
while (top>-1) /*栈不空时循环 */
{ if (St[top].tag==1) /*未计算出栈顶元素的 vf值 */
{ if (St[top].vn==1) /*(1)式 */
{ St[top].vf=1;
St[top].tag=0;
}
else /*(2)式 */
{ top++;
St[top].vn=St[top-1].vn-1; St[top].tag=1;
}
}
else if (St[top].tag==0) /*已计算出 vf值 */
{ St[top-1].vf=St[top-1].vn*St[top].vf; /*(2)式 */
St[top-1].tag=0;
top--;
}
if (top==0 && St[top].tag==0)
/*栈中只有一个已求出 vf的元素时退出循环 */
break;
}
return(St[top].vf);
}
本章小结本章基本学习要点如下：
（ 1） 理解递归的定义和递归模型 。
（ 2） 重点掌握递归的执行过程 。
（ 3） 掌握递归设计的一般方法 。
（ 4） 掌握消除递归的基本方法 。
（ 5）灵活运用递归算法解决一些较复杂应用问题。
练习教材中 p129的习题 1和 2。
