第5章递归 递归与递归程序设计 >递归程序执行过程的分析 >递归程序到非递归程序的转换 >递归程序设计的应用实例
第5章 递 归 ➢递归与递归程序设计 ➢递归程序到非递归程序的转换 ➢递归程序设计的应用实例 ➢递归程序执行过程的分析
51递归与递归程序设计 在一个函数的定义中出现了对自己本身的调用, 称之为直接递归;或者一个函数p的定义中包含了 对函数q的调用,而q的实现过程又调用了p,即函 数调用形成了一个环状调用链,这种方式称之为间接 递归。递归技术在算法和程序设计中是一种十分有 用的技术,许多高级程序设计语言均提供了支持递 归定义的机制和手段。 例1试编一个递归函数,求正整数n的阶乘值n!。 用 fact(n)表示n的阶乘值,据阶乘的数学定义可知: 1 n=0 fact(n)= n*fact(n-1) n>0
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(intn) nt m; if (n==0) return(1); else i m-n*Fact(n-1); return(m);) 例2试编一个递归函数,求第n项 Fibonacci级数的 值 假设使用 Fiona()表示第n项 Fibonacci级数的值, 根据 Fibonacci级数的计算公式 n=1 Fibona(n)=l 1 n=2 Fibona(n-1)+Fibona n-2) n>2
该问题的算法为： 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 i int m; if(n==1) return(1); else if(n==2) return ( 1); else i m=Fibona(n-1)+ Fibona(n-2); return(m);
该问题的算法为： 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)在不满足递归出口的情况下,根据所求解问题 的性质,将原问题分解成若干子问题,这些子问题 的结构与原问题的结构相同,但规模较原问题小。 子问题的求解通过以一定的方式修改参数进行函数 自身调用加以实现,然后将子问题的解组合成原问 题的解。递归调用时,参数的修改最终必须保证递 归出囗得以满足
递归程序设计具有以下两个特点： （1）具备递归出口。递归出口定义了递归的终止条 件，当程序的执行使它得到满足时，递归执行过程 便终止。有些问题的递归程序可能存在几个递归出 口； （2）在不满足递归出口的情况下，根据所求解问题 的性质，将原问题分解成若干子问题，这些子问题 的结构与原问题的结构相同，但规模较原问题小。 子问题的求解通过以一定的方式修改参数进行函数 自身调用加以实现，然后将子问题的解组合成原问 题的解。递归调用时，参数的修改最终必须保证递 归出口得以满足
5.2递归程序执行过程的分析 在递归程序的运行过程中,系统内部设立了一个栈,用于 存放每次函数调用与返回所需的各种数据,主要包括:函数 调用执行完成时的返回地址、函数的返回值、每次函数调用 的实在参数和局部变量。 在递归程序的执行过程中,每当执行函数调用时,必须完 成以下任务: 1)计算当前被调用函数每个实在参数的值 (2)为当前被调用的函数分配一片存储空间,用于存放其 所需的各种数据,并将这片存储空间的首地址压入栈中; (3)将当前被调用函数的实在参数、将来当前函数执行完 毕后的返回地址等数据存入上述所分配的存储空间中; (4)控制转到被调用函数的函数体,从其第一个可执行的 语句开始执行
5．2 递归程序执行过程的分析 在递归程序的运行过程中，系统内部设立了一个栈，用于 存放每次函数调用与返回所需的各种数据，主要包括：函数 调用执行完成时的返回地址、函数的返回值、每次函数调用 的实在参数和局部变量。 在递归程序的执行过程中，每当执行函数调用时，必须完 成以下任务： （1）计算当前被调用函数每个实在参数的值； （2）为当前被调用的函数分配一片存储空间，用于存放其 所需的各种数据，并将这片存储空间的首地址压入栈中； （3）将当前被调用函数的实在参数、将来当前函数执行完 毕后的返回地址等数据存入上述所分配的存储空间中； （4）控制转到被调用函数的函数体，从其第一个可执行的 语句开始执行
当从被调用的函数返回时,必须完成以下任务 (1)如果被调用的函数有返回值,则记下该返回值, 同时通过栈顶元素到该被调用函数对应的存储空间 中取出其返回地址 (2)把分配给被调用函数的那片存储空间回收,栈 顶元素出栈; (3)按照被调用函数的返回地址返回到调用点,若 有返回值,还必须将返回值传递给调用者,并继续 程序的执行
当从被调用的函数返回时，必须完成以下任务： （1）如果被调用的函数有返回值，则记下该返回值， 同时通过栈顶元素到该被调用函数对应的存储空间 中取出其返回地址； （2）把分配给被调用函数的那片存储空间回收，栈 顶元素出栈； （3）按照被调用函数的返回地址返回到调用点，若 有返回值，还必须将返回值传递给调用者，并继续 程序的执行
例3试编写一个递归函数,在第一行打印输出1个1, 在第二行打印输出2个2,…在第n行打印输出n 个n。例如,当n=5时,调用该函数的输出结果为: 22 333 4444 55555 该问题的算法为 print(intn) i int i; if(n!=0) i print(n-1); for(i=1; i<=n; i++ printf("%d",n) printf("\n");
例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(O) print(2 (10) (3) print(3 for(i=1;i<=2;i++ print(4 printf("%od,, 2) (8) Printf("n”); for(i=1;i<=3;i++) (61 printf(%d°3 → Printf(n”); Print(5) for(i=1;i<=4;i++) printf( %od, 4) (4)L printf(n?); for(i=1;i<=5;i++) printf("%od”,5) (2)pint(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)
例4 So Fibona(5) 5 (18) m=Fibona(4)+Erbona(3; return(m) (12) (2) m=Fibona(3)+Fibona(2): /3)(17) 2 m=Fibona(2)+Fiona(1) return(m)i return(m) 8)2 (9)(00 (13 m=Fibona (2)+Fibona(1) (14) return(1) return(m);t- return (1)return(1 (5)1(6 return(1) return (1) Fiona(5)的执行过程
S Fibona(5) 0 (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: