第五章 递归
例题1：编写一个递归过程，它读入一串任意长的字符串，该串字符以”.”作为结束,要求打印出它们的倒序字符串.
解：
依题意，首先获取用户按键，如果不是’.’字符，则递归调用该过程，否则显示该字符。实现本题功能的过程如下：
void reverse（）
{
scanf（”%c”，&ch）；
if（ch！=’.’）
{
reverse；
printf（”%c”，ch）；
}
}
例题2：求两个正整数m和n的最大公约数可以用如下gcd（m，n）公式表示：
- (1)编写一个计算gcd（m，n）的递归过程；
- (2)将上述过程转换成非递归过程；
- (3)画出计算gcd（20，6）的过程及栈的状态变化，给出计算结果。
解：
int gcd（int m，int n）
{
int k；
if（n>m）return（gcd（n，m））；
else if（n==0）return（m）；
else
{
k=m % n；
return（gcd（n，k））；
}
}
- 将上述递归函数转换成非递归函数时，使用了一个栈，用于存储调用参数和函数值，由于本题很特殊，所有情况的函数值都相等，故不需要保存函数值，且当条件满足即n=0时便退出，这里采用一个两维数组作为栈，其内容如下：
stack[top][1]存储m之值
stack[top][2]存储n之值
由此，实现本题功能的非递归函数如下：
int gcd（int m，int n）
{
int k，top=1；
stack[top][1]=m；
stack[top][2]=n；
while（stack[top][2]！=0）/*循环直到n=0为止*/
{
/*若m<n，则（n，m）入栈*/
if（stack[top][1]<stack[top][2]）
{
k=stack[top][1]；
top++；
stack[top][2]=stack[top-1][2]；
stack[top][2]=k；
}
else/*否则，（n，m % n）入栈*/
{
k=stack[top][1] % stack[top][2]；
top++；
stack[top][1]=stack[top-1][1]；
stack[top][2]=k；
}
}
return（stack[top][1]）；
}
本题亦可采用直接转换法得到如下非递归函数gcd2( )：
int gcd2（int m，int n）
{
int r；
do
{
r=m % n；
m=n；
n=r；
} while（r！=0）；
return（m）；
}
- 依照（2）的非递归函数gcd（）的执行过程，计算gcd（20，6）之值栈变化过程如图5.1所示。
图5.1计算gcd（20，6）的过程及栈的状态变化
例题3：设某一函数定义如下：
（1）编写一个递归函数计算给定x的M（x）的值；
（2）编写一个非递归函数计算给定x的M（x）的值。
解：
（1）本函数是一个递归函数，其递归出口是：
M（x）= x-10x>100
递归体是：
M（M（x+11））x ≤100
实现本题功能的递归函数如下：
intm ( intx )
{
inty;
if ( x>100 )return(x-10 );
else
{
y =m(x+11) ;
return (m (y ));
}
}
（2）非递归函数采用直接方法，用level记录调用的层数，当level为0时，结果便计算出来了，实现本题功能的非递归函数如下：
intm1( intx )
{
intlevel=1,y;
if ( x>100)return (x-10);
else
{
level++;
y=x+11;
}
while ( level>0)
{
if ( y>100 )/*参数y小于100时，层树减1，y=y-12*/
{
level--;y=y-10;
}
else/*否则层数level增1，参数y=y+11*/
{
level++;y=y+11;
}
}
return (y );/*层数level伪时，y即为最终计算的函数值*/
} |
