2021年递归递归递归.ppt

第1讲　递 归
递归与递归程序设计
递归程序设计的应用实例
递归程序执行过程的分析
*
递归递归递归
*
(1)直接递归在一个函数的定义中出现了对自己本身的调用。(2)间接递归一个函数p的定义中包含了对函数q的调用，而q的实现过程又调用了p，即函数调用形成了一个环状调用链。
递归与递归程序设计
直接递归调用
间接递归调用
*
递归递归递归
*
例1 试编一个递归函数，求正整数n的阶乘值n！。用fact(n)表示n的阶乘值，据阶乘的数学定义可知：
 1 n=0或n=1 fact(n) =  n*fact(n-1) n>1
递归函数定义的一般算法：
f(x)=
终了公式
递归公式
*
递归递归递归
*
该问题的算法为： int Fact ( int n ){ if (n==0||n==1) return 1; else return n*Fact(n-1); }
递归终止条件
转换成实参值不同的同一问题解
*
递归递归递归
*
在递归程序的执行过程中，每当执行函数调用时，必须完成以下任务：（1）计算当前调用函数时的实参值；（2）为当前被调函数分配一片存储空间，并将这片存储空间的首地址压入堆栈中；（3）将当前被调函数的实参、调用后返回到主调函数代码的地址等数据存入上述所分配的存储空间中；（4）控制转到当前被调用函数的函数体，从其第一个可执行的语句开始执行。
递归程序执行过程的分析
*
递归递归递归
*
当从被调用的函数返回时，必须完成以下任务： （1）如果被调函数有返回值，则记下该返回值，同时通过栈顶元素到该被调用函数对应的存储空间中取出其返回地址；（2）把分配给被调函数的那片存储空间回收，栈顶元素出栈；（3）按照被调函数的返回地址返回到调用点，若有返回值，还必须将返回值传递给调用者，并继续程序的执行。
*
递归递归递归
*
void main()
{ long m;
m=Fact(4);
printf(“\n 4!=%ld”,m);
}
递归调用过程分析：
Fact (n=4)
return 4*Fact(3);
Fact(n=3)
return 3*Fact(2);
Fact(n=2)
return 2*Fact(1);
Fact(n=1)
return 1;
2
6
24
调用
返回
调用
调用
调用
*
递归递归递归
*
例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 ) { if (n==1|| n==2)  return 1; else return Fibona(n-1)+ Fibona(n-2); }
*
递归递归递归
*
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)