文档介绍：第第55章章递递归归
Ø递归与递归程序设计
Ø递归程序执行过程的分析
Ø递归程序到非递归程序的转换
Ø递归程序设计的应用实例
递归与递归程序设计递归与递归程序设计
在一个函数的定义中出现了对自己本身的调用,
称之为直接递归;或者一个函数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 试编一个递归函数,i级数的值。
假设使用Fibona(n)i级数的值,
i级数的计算公式:
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)在不满足递归出口的情况下,根据所求解问题
的性质,将原问题分解成若干子问题,这些子问题
的结构与原问题的结构相同,但规模较原问题小。
子问题的求解通过以一定的方式修改参数进行函数
自身调用加以实现,然后将子问题的解组合成原问
题的解。递归调用时,参数的修改最终必须保证递
归出口得以满足。
55..22 递归程序递归程序执行执行过程的分过程的分析析
在递归程序的运行过程中,系统内部设立了一个栈,用
于存放每次函数调用与返回所需的各种数据,主要包括:函
数调用执行完成时的返回地址、函数的返回值、每次函数调
用的实在参数和局部变量。
在递归程序的执行过程中,每当执行函数调用时,必须
完成以下任务:
(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");}
}
(9) print(0)
(7) print(1)
(5)
print(2)
(10)
(3)
print(3)
(1) for(i=1;i<=2;i++)
print(4) printf(“%d”,2)
(8) Printf(“\n”);
for(i=1;i<=3;i++)
(6) printf(“%d”,3)
Printf(“\n”);
Pr