第 5章 递 归
递归与递归程序设计
递归程序到非递归程序的转换
递归程序设计的应用实例
递归程序执行过程的分析
5.1 递归与递归程序设计在一个函数的定义中出现了对自己本身的调用，
称之为 直接递归 ；或者一个函数 p的定义中包含了对函数 q的调用，而 q的实现过程又调用了 p，即函数调用形成了一个环状调用链,这种方式称之为 间接递归 。递归技术在算法和程序设计中是一种十分有用的技术，许多高级程序设计语言均提供了支持递归定义的机制和手段。
例 1 试编一个递归函数，求正整数 n的阶乘值 n！。
用 fact(n)表示 n的阶乘值，据阶乘的数学定义可知：
1 n=0
fact(n) =
n*fact(n-1) n>0
该问题的算法为,int Fact ( int n )
{ int m;
if (n= =0) return(1);
else
{ m=n*Fact(n-1);
return(m); }
}
例 2 试编一个递归函数，求第 n项 Fibonacci级数的值。
假设使用 Fibona(n)表示第 n项 Fibonacci级数的值，
根据 Fibonacci级数的计算公式：
1 n=1
Fibona(n)= 1 n=2
Fibona(n-1)+ Fibona(n-2) n>2
该问题的算法为：
int Fibona ( int n )
{ int m;
if (n= =1) return (1);
else if (n= =2) return(1);
else
{ m=Fibona(n-1)+ Fibona(n-2);
return (m);
}
}
递归程序设计具有以下 两个特点,
（ 1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，递归执行过程便终止。有些问题的递归程序可能存在几个递归出口；
（ 2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题,这些子问题的结构与原问题的结构相同，但规模较原问题小。
子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。
5,2 递归程序执行过程的分析在递归程序的运行过程中，系统内部设立了一个栈，用于存放每次函数调用与返回所需的各种数据，主要包括：函数调用执行完成时的返回地址、函数的返回值、每次函数调用的实在参数和局部变量。
在递归程序的执行过程中，每当执行函数调用时，必须完成以下任务：
（ 1）计算当前被调用函数每个实在参数的值；
（ 2）为当前被调用的函数分配一片存储空间，用于存放其所需的各种数据，并将这片存储空间的首地址压入栈中；
（ 3）将当前被调用函数的实在参数、将来当前函数执行完毕后的返回地址等数据存入上述所分配的存储空间中；
（ 4）控制转到被调用函数的函数体，从其第一个可执行的语句开始执行。
当从被调用的函数返回时，必须完成以下任务：
（ 1）如果被调用的函数有返回值，则记下该返回值，
同时通过栈顶元素到该被调用函数对应的存储空间中取出其返回地址；
（ 2）把分配给被调用函数的那片存储空间回收，栈顶元素出栈；
（ 3）按照被调用函数的返回地址返回到调用点，若有返回值，还必须将返回值传递给调用者，并继续程序的执行。
例 3 试编写一个递归函数，在第一行打印输出 1个 1，
在第二行打印输出 2个 2,…… 在第 n行打印输出 n个
n。例如，当 n=5时，调用该函数的输出结果为：
1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
该问题的算法为,print ( int n )
{ int i;
if (n!=0)
{ print(n-1);
for(i=1;i<=n;i++)
printf("%d",n);
printf("\n");}
}
Print(5)
print(4)
for(i=1;i<=5;i++)
printf(“%d”,5)
printf(“\n”);
print(3)
for(i=1;i<=4;i++)
printf(“%d”,4)
printf(“\n”);
print(2)
for(i=1;i<=3;i++)
printf(“%d”,3)
Printf(“\n”);
print(1)
for(i=1;i<=2;i++)
printf(“%d”,2)
Printf(“\n”);
print(0)
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
Fibona(5)S0
(1)
m=Fibona(4)+Fibona(3);
return(m);
m=Fibona(3)+Fibona(2);
return(m) ;
(2)
m=Fibona(2)+Fibona(1);
return(m);
(3)
m=Fibona(2)+Fibona(1);
return(m); 1
return(1)
(4)
return(1)
(5)
return(1)
(6) (7)
(8) (9)
return(1) return(1)
(10)
Fibona(5)的执行过程
S1
S2
S3
1 1
1
2
3
(11)
(12)
(13)
(14)
1 (15)
(17)
(18)
5
2
例 4:
5.3 递归程序到非递归程序的转换采用递归方式实现问题的算法程序具有结构清晰、可读性好、易于理解等优点，但递归程序较之非递归程序无论是空间需求还是时间需求都更高，
因此在希望节省存储空间和追求执行效率的情况下，
人们更希望使用非递归方式实现问题的算法程序；
另外，有些高级程序设计语言没有提供递归的机制和手段，对于某些具有递归性质的问题（简称递归问题）无法使用递归方式加以解决，必须使用非递归方式实现。因此，本小节主要研究递归程序到非递归程序的转换方法。
一般而言，求解递归问题有两种方式：
（ 1）在求解过程中直接求值，无需回溯。称这类递归问题为 简单递归问题 ；
（ 2）另一类递归问题在求解过程中不能直接求值，
必须进行试探和回溯，称这类递归问题为 复杂递归问题 。
两类递归问题在转换成非递归方式实现时所采用的方法是不同的。通常简单递归问题可以采用 递推方法 直接求解；而复杂递归问题由于要进行回溯，
在实现过程中必须 借助栈 来管理和记忆回溯点。
5.3.1 简单递归程序到非递归程序的转换采用 递归技术 求解问题的算法程序是 自顶向下 产生计算序列，其缺点之一是导致程序执行过程中许多重复的函数调用。 递推技术 同样以分划技术为基础，它也要求将需求解的问题分划成若干与原问题结构相同、但规模较小的子问题；与递归技术不同的是，递推方法是采用 自底向上 的方式产生计算序列，其首先计算规模最小的子问题的解，然后在此基础上依次计算规模较大的子问题的解，直到最后产生原问题的解。由于求解过程中每一步新产生的结果总是直接以前面已有的计算结果为基础，避免了许多重复的计算，因而递推方法产生的算法程序比递归算法具有更高的效率。
简单递归问题非递归实现的基本思想,将原问题分解成若干 结构与原问题相同，但规模较小的子问题，
并 建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录递推关系的每个子问题的解；
程序的执行便是根据递推关系，不断修改这些变量的值，使之成为更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。
例 5 采用非递归方式实现求正整数 n的阶乘值。
仍使用 Fact(n)表示 n的阶乘值。要求解 Fact(n)
的值，可以考虑 i从 0开始，依次取 1,2,……,一直到 n，分别求 Fact(i)的值，且保证求解 Fact(i)时总是以前面已有的求解结果为基础；当 i=n 时，
Fact(i)的值即为所求的 Fact(n)的值。
根据阶乘的递归定义，不失一般性，显然有以下递推关系成立：
1 i=0
Fact(i)=
i* Fact(i-1) i>0
上述递推关系表明 Fact(i)是建立于 Fact(i-1)的基础上的，在求解 Fact(i)时子问题只有一个 Fact(i-
1)，且整个 Fact(n)的求解过程无需回溯，因此该问题属于简单递归问题，可以使用递推技术加以实现，
实现过程中只需定义一个变量 fac始终记录子问题
Fact(i-1)的值。初始时,i=1,fac= Fact(i-1)=
Fact(0)=1；在此基础上根据以上递推关系不断向前递推，使 i的值加大，直至 i=n为止。
阶乘问题的非递归算法的实现如下：
int Fact ( int n )
{
int i,fac;
fac=1;/*将变量 fac初始化为 Fact(0)的值 */
for (i=1;i<=n; ++i) fac =i*fac;
/*根据递推关系进行递推 */
return(fac);
}
例 6 试编写两个函数，分别使用递归方式和非递归方式求第 n阶勒让德多项式的值。
已知勒让德多项式的递归定义如下：
1 n=0
pn(x)= x n=1
((2n-1)?x?pn-1(x)?(n-1)?pn-2(x))/n n>1
递归实现算法：
float p(int n,float x)
{ float p1,p2;
if (n==0) return(1.0);
else if (n==1) return(x);
else { p1=(2*n-1)*x*p(n-1,x);
p2=(n-1)*p(n-2,x);
return((p1-p2)/n);
}
}
下面考虑该问题的非递归实现：根据勒让德多项式的定义，当 n>1时，第 n阶多项式的值是建立在第 n-1
阶多项式的值和第 n-2阶多项式的值的基础上。考虑一般情况，当 i>1时，第 i阶多项式的值应该建立在第 i-1
阶多项式的值和第 i-2阶多项式的值的基础上。如果仍然采用 p(n,x)表示第 n阶勒让德多项式的值，则在 i>1
的情况下有如下递推关系成立：
p(i,x)=((2i-1)?x?p(i-1,x)?(i-1)?p(i-2,x))/i
显然，可以利用以上递推关系，从 i=2开始，逐步增大 i的值，依次求解第 i阶勒让德多项式的值；当 i=n
时，便求到了 p(n,x)的值。在整个求解过程中不需要进行试探和回溯，因而该问题属于简单递归问题，完全可以使用递推技术加以实现。
在具体实现时可以定义两个变量 pre1和 pre2，
分别记录上述递推关系中两个子问题的解，即
pre1=p(i-2,x),pre2=p(i-1,x)，且 pre1和 pre2的值始终随着 i的值的改变而发生变化：每当新求出第
i阶多项式的值后,i的值要增加 1，而在此之前应该修改 pre1和 pre2的值，用 pre1记录 pre2当前的值，
而用 pre2记录新求出的多项式的值，直至 i=n。
float p ( int n,float x )
{
float pre1,pre2,a,b,valuep;
int i;
if (n==0) return(1.0);
else if (n==1) return(x);
else {pre1=1.0;
pre2=x;
for (i=2;i<=n;++i)
{
a=2*i-1;
b=i-1;
valuep=(a*pre2*x-b*pre1)/i;
pre1=pre2;
pre2=valuep;
}
return(valuep);
}
}
5.3.2 复杂递归程序到非递归程序的转换复杂递归问题在求解的过程中无法保证求解动作一直向前，往往需要设臵一些回溯点，当求解无法进行下去或当前处理的工作已经完成时，必须退回到所设臵的回溯点，继续问题的求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，
经常使用栈来记录和管理所设臵的回溯点。
例 7 按中点优先的顺序遍历线性表问题：已知线性表 list以顺序存储方式存储，要求按以下顺序输出
list中所有结点的值：首先输出线性表 list中点位臵上的元素值，然后输出中点左部所有元素的值，
再输出中点右部所有元素的值；而无论输出中点左部所有元素的值还是输出中点右部所有元素的值，
也均应遵循以上规律。
例如，已知数组 list中元素的值为：
18 32 4 9 26 6 10 30 12 8 45
则 list中元素按中点优先顺序遍历的输出结果为：
6 4 18 32 9 26 12 10 30 8 45
试采用递归和非递归算法实现该遍历问题。
递归实现算法如下,
#define MAXSIZE 20
typedef int listarr[MAXSIZE];
void listorder(listarr list,int left,int right)
{ /*将数组段 list[left..right]的元素按中点优先顺序输出 */
int mid;
if (left<=right)
{ mid=(left+right)/2;
printf("%4d",list[mid]);
listorder(list,left,mid-1);
listorder(list,mid+1,right);
}
}
Left mid-1 mid mid+1 right
下面考虑该问题的非递归实现：在线性表的遍历过程中，输出中点的值后，中点将线性表分成前半部分和后半部分。接下来应该考虑前半部分的遍历，但在进入前半部分的遍历之前，应该将后半部分保存起来，以便访问完前半部分所有元素后，再进入后半部分的访问，即在此设臵一个回溯点，该回溯点应该进栈保存，具体实现时，只需将后半部分起点和终点的下标进栈即可，栈中的每个元素均代表一个尚未处理且在等待被访问的数组段。对于每一个当前正在处理的数组（数组段）均应采用以上相同的方式进行处理，
直到当前正在处理的数组（数组段）为空，此时应该进行回溯，而回溯点恰巧位于栈顶。于是只要取出栈顶元素，将它所确定的数组段作为下一步即将遍历的对象，继续线性表的遍历，直到当前正在处理的数组段为空且栈亦为空（表示已无回溯点），算法结束。
#define MAXSIZE 20
typedef int listarr[MAXSIZE];
void listorder(listarr list,int left,int
right)
{ typedef struct {
int l; /*存放待处理数组段的起点下标 */
int r; /*存放待处理数组段的终点下标 */
} stacknode; /*栈中每个元素的类型 */
stacknode stack[MAXSIZE];
int top,i,j,mid; /*top为栈顶指针 */
if (left<=right) /*数组段不为空 */
{ top= -1; i=left; j=right;
while (i<=j || top!=-1)
{/*当前正在处理的数组段非空或栈非空 */
if (i<=j)
{ mid=(i+j)/2;
printf(“%4d”,list[mid]);
++top; stack[top].l=mid+1;
stack[top].r=j; j=mid-1;
}
else
{ /*当前正在处理的数组段为空时进行回溯 */
i=stack[top].l;
j=stack[top].r;
--top;
}
}
}
}
5,4 递归程序设计的应用实例例 9 设计一个递归函数，将一个正整数 n转换成字符串。例如，若 n=456，则函数输出的结果为,456”。
n的位数不确定，可以为任意位数的整数。
void convert(int n)
{ int i;
char ch;
if ((i=n/10)!=0)
convert(i);
ch=( n % 10 )+ '0';
putchar(ch);
}
例 10 试编写一个递归函数，求两个正整数 m和 n的最大公约数，其中最大公约数 gcd(m,n)的求解公式为：
gcd(n,m) m<n
gcd(m,n)= m n=0
gcd( n,m % n ) 其它情形
int gcd(int m,int n)
{ int k;
if (n==0) return(m);
else if (n>m) return(gcd(n,m));
else
{ k=m%n;
return(gcd(n,k));
}
}
例 11 已知整型数组 a，试编写一个递归函数，实现数组 a中所有元素的逆转。例如，假设 a中元素为：
56 21 34 9 12 33 2 98 16 83
逆转后 a中所有元素的排列顺序为：
83 16 98 2 33 12 9 34 21 56
#define MAXSIZE 20
typedef int list[MAXSIZE];
int length;
void reverse ( list a,int l,int r )
{ /*将数组段 a[l..r]的元素进行逆转 */
int temp;
if (l<r)
{ reverse (a,l+1,r-1 );
temp=a[l]; a[l]=a[r]; a[r]=temp;
}
}
l l+1 r-1 r
递归与递归程序设计
递归程序到非递归程序的转换
递归程序设计的应用实例
递归程序执行过程的分析
5.1 递归与递归程序设计在一个函数的定义中出现了对自己本身的调用，
称之为 直接递归 ；或者一个函数 p的定义中包含了对函数 q的调用，而 q的实现过程又调用了 p，即函数调用形成了一个环状调用链,这种方式称之为 间接递归 。递归技术在算法和程序设计中是一种十分有用的技术，许多高级程序设计语言均提供了支持递归定义的机制和手段。
例 1 试编一个递归函数，求正整数 n的阶乘值 n！。
用 fact(n)表示 n的阶乘值，据阶乘的数学定义可知：
1 n=0
fact(n) =
n*fact(n-1) n>0
该问题的算法为,int Fact ( int n )
{ int m;
if (n= =0) return(1);
else
{ m=n*Fact(n-1);
return(m); }
}
例 2 试编一个递归函数，求第 n项 Fibonacci级数的值。
假设使用 Fibona(n)表示第 n项 Fibonacci级数的值，
根据 Fibonacci级数的计算公式：
1 n=1
Fibona(n)= 1 n=2
Fibona(n-1)+ Fibona(n-2) n>2
该问题的算法为：
int Fibona ( int n )
{ int m;
if (n= =1) return (1);
else if (n= =2) return(1);
else
{ m=Fibona(n-1)+ Fibona(n-2);
return (m);
}
}
递归程序设计具有以下 两个特点,
（ 1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，递归执行过程便终止。有些问题的递归程序可能存在几个递归出口；
（ 2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题,这些子问题的结构与原问题的结构相同，但规模较原问题小。
子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。
5,2 递归程序执行过程的分析在递归程序的运行过程中，系统内部设立了一个栈，用于存放每次函数调用与返回所需的各种数据，主要包括：函数调用执行完成时的返回地址、函数的返回值、每次函数调用的实在参数和局部变量。
在递归程序的执行过程中，每当执行函数调用时，必须完成以下任务：
（ 1）计算当前被调用函数每个实在参数的值；
（ 2）为当前被调用的函数分配一片存储空间，用于存放其所需的各种数据，并将这片存储空间的首地址压入栈中；
（ 3）将当前被调用函数的实在参数、将来当前函数执行完毕后的返回地址等数据存入上述所分配的存储空间中；
（ 4）控制转到被调用函数的函数体，从其第一个可执行的语句开始执行。
当从被调用的函数返回时，必须完成以下任务：
（ 1）如果被调用的函数有返回值，则记下该返回值，
同时通过栈顶元素到该被调用函数对应的存储空间中取出其返回地址；
（ 2）把分配给被调用函数的那片存储空间回收，栈顶元素出栈；
（ 3）按照被调用函数的返回地址返回到调用点，若有返回值，还必须将返回值传递给调用者，并继续程序的执行。
例 3 试编写一个递归函数，在第一行打印输出 1个 1，
在第二行打印输出 2个 2,…… 在第 n行打印输出 n个
n。例如，当 n=5时，调用该函数的输出结果为：
1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
该问题的算法为,print ( int n )
{ int i;
if (n!=0)
{ print(n-1);
for(i=1;i<=n;i++)
printf("%d",n);
printf("\n");}
}
Print(5)
print(4)
for(i=1;i<=5;i++)
printf(“%d”,5)
printf(“\n”);
print(3)
for(i=1;i<=4;i++)
printf(“%d”,4)
printf(“\n”);
print(2)
for(i=1;i<=3;i++)
printf(“%d”,3)
Printf(“\n”);
print(1)
for(i=1;i<=2;i++)
printf(“%d”,2)
Printf(“\n”);
print(0)
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
Fibona(5)S0
(1)
m=Fibona(4)+Fibona(3);
return(m);
m=Fibona(3)+Fibona(2);
return(m) ;
(2)
m=Fibona(2)+Fibona(1);
return(m);
(3)
m=Fibona(2)+Fibona(1);
return(m); 1
return(1)
(4)
return(1)
(5)
return(1)
(6) (7)
(8) (9)
return(1) return(1)
(10)
Fibona(5)的执行过程
S1
S2
S3
1 1
1
2
3
(11)
(12)
(13)
(14)
1 (15)
(17)
(18)
5
2
例 4:
5.3 递归程序到非递归程序的转换采用递归方式实现问题的算法程序具有结构清晰、可读性好、易于理解等优点，但递归程序较之非递归程序无论是空间需求还是时间需求都更高，
因此在希望节省存储空间和追求执行效率的情况下，
人们更希望使用非递归方式实现问题的算法程序；
另外，有些高级程序设计语言没有提供递归的机制和手段，对于某些具有递归性质的问题（简称递归问题）无法使用递归方式加以解决，必须使用非递归方式实现。因此，本小节主要研究递归程序到非递归程序的转换方法。
一般而言，求解递归问题有两种方式：
（ 1）在求解过程中直接求值，无需回溯。称这类递归问题为 简单递归问题 ；
（ 2）另一类递归问题在求解过程中不能直接求值，
必须进行试探和回溯，称这类递归问题为 复杂递归问题 。
两类递归问题在转换成非递归方式实现时所采用的方法是不同的。通常简单递归问题可以采用 递推方法 直接求解；而复杂递归问题由于要进行回溯，
在实现过程中必须 借助栈 来管理和记忆回溯点。
5.3.1 简单递归程序到非递归程序的转换采用 递归技术 求解问题的算法程序是 自顶向下 产生计算序列，其缺点之一是导致程序执行过程中许多重复的函数调用。 递推技术 同样以分划技术为基础，它也要求将需求解的问题分划成若干与原问题结构相同、但规模较小的子问题；与递归技术不同的是，递推方法是采用 自底向上 的方式产生计算序列，其首先计算规模最小的子问题的解，然后在此基础上依次计算规模较大的子问题的解，直到最后产生原问题的解。由于求解过程中每一步新产生的结果总是直接以前面已有的计算结果为基础，避免了许多重复的计算，因而递推方法产生的算法程序比递归算法具有更高的效率。
简单递归问题非递归实现的基本思想,将原问题分解成若干 结构与原问题相同，但规模较小的子问题，
并 建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录递推关系的每个子问题的解；
程序的执行便是根据递推关系，不断修改这些变量的值，使之成为更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。
例 5 采用非递归方式实现求正整数 n的阶乘值。
仍使用 Fact(n)表示 n的阶乘值。要求解 Fact(n)
的值，可以考虑 i从 0开始，依次取 1,2,……,一直到 n，分别求 Fact(i)的值，且保证求解 Fact(i)时总是以前面已有的求解结果为基础；当 i=n 时，
Fact(i)的值即为所求的 Fact(n)的值。
根据阶乘的递归定义，不失一般性，显然有以下递推关系成立：
1 i=0
Fact(i)=
i* Fact(i-1) i>0
上述递推关系表明 Fact(i)是建立于 Fact(i-1)的基础上的，在求解 Fact(i)时子问题只有一个 Fact(i-
1)，且整个 Fact(n)的求解过程无需回溯，因此该问题属于简单递归问题，可以使用递推技术加以实现，
实现过程中只需定义一个变量 fac始终记录子问题
Fact(i-1)的值。初始时,i=1,fac= Fact(i-1)=
Fact(0)=1；在此基础上根据以上递推关系不断向前递推，使 i的值加大，直至 i=n为止。
阶乘问题的非递归算法的实现如下：
int Fact ( int n )
{
int i,fac;
fac=1;/*将变量 fac初始化为 Fact(0)的值 */
for (i=1;i<=n; ++i) fac =i*fac;
/*根据递推关系进行递推 */
return(fac);
}
例 6 试编写两个函数，分别使用递归方式和非递归方式求第 n阶勒让德多项式的值。
已知勒让德多项式的递归定义如下：
1 n=0
pn(x)= x n=1
((2n-1)?x?pn-1(x)?(n-1)?pn-2(x))/n n>1
递归实现算法：
float p(int n,float x)
{ float p1,p2;
if (n==0) return(1.0);
else if (n==1) return(x);
else { p1=(2*n-1)*x*p(n-1,x);
p2=(n-1)*p(n-2,x);
return((p1-p2)/n);
}
}
下面考虑该问题的非递归实现：根据勒让德多项式的定义，当 n>1时，第 n阶多项式的值是建立在第 n-1
阶多项式的值和第 n-2阶多项式的值的基础上。考虑一般情况，当 i>1时，第 i阶多项式的值应该建立在第 i-1
阶多项式的值和第 i-2阶多项式的值的基础上。如果仍然采用 p(n,x)表示第 n阶勒让德多项式的值，则在 i>1
的情况下有如下递推关系成立：
p(i,x)=((2i-1)?x?p(i-1,x)?(i-1)?p(i-2,x))/i
显然，可以利用以上递推关系，从 i=2开始，逐步增大 i的值，依次求解第 i阶勒让德多项式的值；当 i=n
时，便求到了 p(n,x)的值。在整个求解过程中不需要进行试探和回溯，因而该问题属于简单递归问题，完全可以使用递推技术加以实现。
在具体实现时可以定义两个变量 pre1和 pre2，
分别记录上述递推关系中两个子问题的解，即
pre1=p(i-2,x),pre2=p(i-1,x)，且 pre1和 pre2的值始终随着 i的值的改变而发生变化：每当新求出第
i阶多项式的值后,i的值要增加 1，而在此之前应该修改 pre1和 pre2的值，用 pre1记录 pre2当前的值，
而用 pre2记录新求出的多项式的值，直至 i=n。
float p ( int n,float x )
{
float pre1,pre2,a,b,valuep;
int i;
if (n==0) return(1.0);
else if (n==1) return(x);
else {pre1=1.0;
pre2=x;
for (i=2;i<=n;++i)
{
a=2*i-1;
b=i-1;
valuep=(a*pre2*x-b*pre1)/i;
pre1=pre2;
pre2=valuep;
}
return(valuep);
}
}
5.3.2 复杂递归程序到非递归程序的转换复杂递归问题在求解的过程中无法保证求解动作一直向前，往往需要设臵一些回溯点，当求解无法进行下去或当前处理的工作已经完成时，必须退回到所设臵的回溯点，继续问题的求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，
经常使用栈来记录和管理所设臵的回溯点。
例 7 按中点优先的顺序遍历线性表问题：已知线性表 list以顺序存储方式存储，要求按以下顺序输出
list中所有结点的值：首先输出线性表 list中点位臵上的元素值，然后输出中点左部所有元素的值，
再输出中点右部所有元素的值；而无论输出中点左部所有元素的值还是输出中点右部所有元素的值，
也均应遵循以上规律。
例如，已知数组 list中元素的值为：
18 32 4 9 26 6 10 30 12 8 45
则 list中元素按中点优先顺序遍历的输出结果为：
6 4 18 32 9 26 12 10 30 8 45
试采用递归和非递归算法实现该遍历问题。
递归实现算法如下,
#define MAXSIZE 20
typedef int listarr[MAXSIZE];
void listorder(listarr list,int left,int right)
{ /*将数组段 list[left..right]的元素按中点优先顺序输出 */
int mid;
if (left<=right)
{ mid=(left+right)/2;
printf("%4d",list[mid]);
listorder(list,left,mid-1);
listorder(list,mid+1,right);
}
}
Left mid-1 mid mid+1 right
下面考虑该问题的非递归实现：在线性表的遍历过程中，输出中点的值后，中点将线性表分成前半部分和后半部分。接下来应该考虑前半部分的遍历，但在进入前半部分的遍历之前，应该将后半部分保存起来，以便访问完前半部分所有元素后，再进入后半部分的访问，即在此设臵一个回溯点，该回溯点应该进栈保存，具体实现时，只需将后半部分起点和终点的下标进栈即可，栈中的每个元素均代表一个尚未处理且在等待被访问的数组段。对于每一个当前正在处理的数组（数组段）均应采用以上相同的方式进行处理，
直到当前正在处理的数组（数组段）为空，此时应该进行回溯，而回溯点恰巧位于栈顶。于是只要取出栈顶元素，将它所确定的数组段作为下一步即将遍历的对象，继续线性表的遍历，直到当前正在处理的数组段为空且栈亦为空（表示已无回溯点），算法结束。
#define MAXSIZE 20
typedef int listarr[MAXSIZE];
void listorder(listarr list,int left,int
right)
{ typedef struct {
int l; /*存放待处理数组段的起点下标 */
int r; /*存放待处理数组段的终点下标 */
} stacknode; /*栈中每个元素的类型 */
stacknode stack[MAXSIZE];
int top,i,j,mid; /*top为栈顶指针 */
if (left<=right) /*数组段不为空 */
{ top= -1; i=left; j=right;
while (i<=j || top!=-1)
{/*当前正在处理的数组段非空或栈非空 */
if (i<=j)
{ mid=(i+j)/2;
printf(“%4d”,list[mid]);
++top; stack[top].l=mid+1;
stack[top].r=j; j=mid-1;
}
else
{ /*当前正在处理的数组段为空时进行回溯 */
i=stack[top].l;
j=stack[top].r;
--top;
}
}
}
}
5,4 递归程序设计的应用实例例 9 设计一个递归函数，将一个正整数 n转换成字符串。例如，若 n=456，则函数输出的结果为,456”。
n的位数不确定，可以为任意位数的整数。
void convert(int n)
{ int i;
char ch;
if ((i=n/10)!=0)
convert(i);
ch=( n % 10 )+ '0';
putchar(ch);
}
例 10 试编写一个递归函数，求两个正整数 m和 n的最大公约数，其中最大公约数 gcd(m,n)的求解公式为：
gcd(n,m) m<n
gcd(m,n)= m n=0
gcd( n,m % n ) 其它情形
int gcd(int m,int n)
{ int k;
if (n==0) return(m);
else if (n>m) return(gcd(n,m));
else
{ k=m%n;
return(gcd(n,k));
}
}
例 11 已知整型数组 a，试编写一个递归函数，实现数组 a中所有元素的逆转。例如，假设 a中元素为：
56 21 34 9 12 33 2 98 16 83
逆转后 a中所有元素的排列顺序为：
83 16 98 2 33 12 9 34 21 56
#define MAXSIZE 20
typedef int list[MAXSIZE];
int length;
void reverse ( list a,int l,int r )
{ /*将数组段 a[l..r]的元素进行逆转 */
int temp;
if (l<r)
{ reverse (a,l+1,r-1 );
temp=a[l]; a[l]=a[r]; a[r]=temp;
}
}
l l+1 r-1 r
