tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

函数的递归调用


递归(Recursion)
函数的嵌套调用有一个特例,即递归调用, 也就是说,在调用一个函数的过程中,又出现 了直接或间接地去调用该函数本身。

2016/3/18

1

递归(Recursion)
C允许一个函数调用其本身。这种调用过程被称作递归(recursion)。它通常把一个 大型复杂的问

题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少 量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归

的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递

归前进段和递归返回段。
#include<stdio.h> void up_and_down(int);
输出如下: Level 1: n location 0022FEE0 Level 2: n location 0022FEC0 Level 3: n location 0022FEA0 Level 4: n location 0022FE80 Level 5: n location 0022FE60 Level 5: n location 0022FE60 Level 4: n location 0022FE80 Level 3: n location 0022FEA0 Level 2: n location 0022FEC0 Level 1: n location 0022FEE0

int main(void) { up_and_down(1); return 0; } void up_and_down(int n) { printf(“Level %d: n location %p\n”,n,&n); if(n<5) up_and_down(n+1); printf(“Level %d: n location %p\n”,n,&n); }
2016/3/18

//#1 //#2
2

程序分析
我们来分析程序中递归的具体工作过程。首先main()使用参数1调用了函数 up_and_down()。于是up_and_down()中形式参量n的值为1,故打印语句#1输出了Level1.然 后,由于n的数值小于4,所以up_and_down()(第1级)使用参数n+1即数值2调用了 up_and_down()(第2级)。这使得n在第2级调用中被赋值为2,打印语句#1输出的是Level2。 与之类似,下面三次调用分别打印出Level3、Level4和Level5。 当开始执行第5级调用时,n的值是5,因此if语句的条件不满足。这时不再继续调用 up_and_down()函数。第5级调用接着执行打印语句#2,即输出Level5,因为n的值是5。现 在函数需要执行return语句,此时第5级调用结束,把控制返回给该函数的调用函数,也就 是第4级调用函数。第4级调用函数中前一个执行过的语句是在if语句中进行第5级调用。因 此,它开始继续执行其后续的代码,即执行打印语句#2,这将会输出Level4,当第4级调用 结束后,第3级调用函数开始继续执行,即输出了Level3.依次类推。 注意,每一级的递归都使用它自己私有的变量n。我们可以通过查看地址的值来得出这 个结论(调用时的Leveln地址和返回时的Leveln地址是相同的)。 如果你还对此感到有些迷惑,可以假想进行了一系列函数调用,即使用fun1()调用 fun2(),fun2()调用fun3(),fun3()调用fun4(), fun4()调用fun5()。Fun5()执行完后, fun4()会继续执行。而fun4()执行完后,fun3()会继续执行。fun3()执行完后,fun2()会 继续执行。最后fun2()返回到fun1()中并执行后续代码。递归过程也是如此,只不过 fun1()、fun2()、fun3()、fun4()、fun5()是相同的函数。

2016/3/18

3

使用递归算法解决问题的条件
?

构成递归需具备的条件

1.把原问题能够分解成为规模 更小的、具有与原问题有着相 同解法(性质)的子问题。

德罗斯特效应—递归的视觉效应

2. 不能无限制地调用本身,须 存在一种简单情境,可以使递 归在简单情境下退出(化简为 非递归状况处理)。 注意:如果一个问题不满 足以上两个条件,那么它就不 能用递归来解决。
4

2016/3/18

递归算法实现的关键
?

递归函数来源于递归算法,递归算法简洁、紧凑 而优雅(elegant)的实现了递归算法。

?

递归的两个要素(写出递归算法的关键)
?

⑴递归式:大问题是如何分解为小问题的,也 称为递归体。每次递归调用必须使用一个更小 的参数值。 ⑵递归出口:确定递归到何时终止;

?

解决递归问题的步骤: 分析问题 ? 递归要素 ? 设计算法
2016/3/18 5

递归算法的应用
? ?

递归算法一般用于解决三类问题:

(1)所求数据的定义是按递归定义的。
?

求阶乘:n!=1×2×3×……×n 或 n!=n×(n-1)! Fact(n) = 1 若n=0 n * Fact(n-1) 若n>0

?

Fibonacci函数: Fib(n) =

0 若n=0 1 若n=1 Fib(n-1) + Fib(n-2) 若n>0
6

2016/3/18

?

(2)数据的结构形式是按递归定义的
? ?

树的遍历 图的搜索

?

(3)递归求解比迭代求解更简单的问题
?
?

八皇后
Hanoi汉诺塔问题

2016/3/18

7

例1 求阶乘
?

n! fact(n) = 1 若n=0 n * fact(n-1) 若n>0

int fact(int n) { if (0 == n) return 1; return n * fact(n-1); }
2016/3/18 8

递归函数 fact( n )的执行过程
fact(3)= 3*fact(2)= 3*2=6 2*fact(1)=
同时有4个函数在运 行,且都未完成

2*1=2

fact(1)=1
main() fact(3) fact(2) fact(1) { .... { .... { .... { .... printf(fact(3)) f=3*fact(2) f=2*fact(1) f=1 } return(f) return(f) return(f) } } }
2016/3/18 9

例2 互质数的判断
? ? ?

如何证明两个整数互质(互为素数)。

例:314159与271828互质的证明。
如果两个整数的最大公约数为1,则两数互质。

2016/3/18

10

例2----欧几里得算法
?

两个整数x和y(x>y)的最大公约数与y和x%y的 最大公约数相同。也叫辗转相除法。 x (当y=0)

gcd(x,y) =

gcd(y, x%y) (x>y 且 x%y不为0)

2016/3/18

11

?

例:314159与271828互为素数的证明。

gcd(314159, 271828) =
gcd(271828, 42331) = gcd(42331, 17842) =

gcd(17842, 6647) =
gcd(6647, 4458) = gcd(4458, 2099) = gcd(2099, 350) = gcd(350, 349) =

gcd(349, 1) =
gcd(1, 0) =1
2016/3/18 12

//欧几里得算法的递归形式 int gcd(int x, int y) { if (y==0) return x; return gcd(y, x%y); }

2016/3/18

13

//欧几里得算法的迭代形式
int gcd(int x, int y) { int r; while (y != 0) { r = y; y = x % y; x = r; } return r; }

2016/3/18

14

例3 Fibonacci函数
0 若n=0 1 若n=1 fib(n-1) + fib(n-2) 若n>0

fib(n) =

?

求 F( 5 ) ? f(5)=f(4)+f(3); ? f(4)=f(3)+f(2); ? f(3)=f(2)+f(1); ? f(2)=f(1)+f(0);
15

2016/3/18

// Fibonacci.c 求Fibonacci数列值的示例算法 #include <stdio.h> int fib(int n); //原型声明 int main() { int i; for (i=0; i<10; i++) { printf("fib(%d): %d\n", i, fib(i)); } return 0; } int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; return fib(n-1) + fib(n-2); } 2016/3/18

16

例4----逆序输出字符串
?

把用户输入的一行字符逆序输出,如输入abc,则 输出cba。 分析:解决这个问题可以分为三步:
第一步:得到用户输入的第一个字符(a);

?

第二步:把余下的字符(ab)逆序输出(bc);
第三步:输出第一个字符(a)即得到(cba)。
?

在上面的算法中第二步性质与原问题相同,规模 变小,此算法即为一个递归算法。 子问题规模缩小到何种程度时才能解决问题呢?
不管输入字符串的长短,最后都有一个回车符,如果字符为回 车符时,问题就解决了。

?

2016/3/18

17

例4----逆序输出字符串
1、得到输入字符中的第一个字符

reverse()=

2、如果字符为’\n’,则直接返回,否则, 调用reverse()函数逆序输出剩余的字符。 再输出第一个字符。

2016/3/18

18

#include <stdio.h> void reverse(); //原型声明 int main() { reverse(); return 0; } void reverse() { char c; c=getchar(); //得到输入字符中的第一个字符 if (c != ?\n?) //如果字符不是?\n?,说明还有问题待解决 { reverse(); //递归调用,逆序输出其余的字串 putchar(c); //输出先前获得字符,完成逆序输出 } }
2016/3/18 19

用户输入 abc\n 则变量c 的值为a

缓冲区中 数据bc\n 则变量c 的值为b

缓冲区中 数据c\n 则变量c 的值为c

缓冲区中 数据\n 则变量c 的值为\n

注意!调用函数和被调用函数都有各自的执行空间,互不干涉!
2016/3/18 20

例5----上台阶
?

楼梯有n级台阶,上楼时一步可以上1级台阶,也 可以一步上2级台阶,编程计算上完这n级台阶一 共有多少种不同的走法。
分析:设n级台阶的走法为f(n) 先考虑上楼梯时第一步怎么走 只有两种情况:上1级和上2级 n级楼梯的不同走法等于这两种情况下不同走法的的总和 第一步上1级时有多少种不同的走法呢?

? ? ? ? ?

?
? ? ?

还有n-1级需要上
剩余的楼梯有多少种不同的走法? 性质相同、规模变小,即f(n-1)种

那么第一步上2级时有多少种不同的走法呢?显然就是f(n-2)种
21

2016/3/18

例5----上台阶
?

f(n)的定义

1

n=1

f()=

2

n=2

f(n-1)+f(n-2)

n>2

2016/3/18

22

#include <stdio.h> int upstairs(int n); //原型声明 int main() { printf(“4级台阶一共有%d种不同的走法。\n”, upstairs(4)); return 0; } int upstairs(int n); { if (n==1 || n==2 ) return n; return f(n-1)+f(n-2); }

2016/3/18

23

int upstairs(int n); { if (n==1 || n==2 ) return n; return f(n-1)+f(n-2); }

upstairs(1)

upstairs(2)

upstairs(2)

upstairs(3)

upstairs(4)
2016/3/18 24

在编写递归调用的函数的时候,一定要把对简 单情境的判断写在最前面,以保证函数调用在检查 到简单情境的时候能够及时地中止递归,否则,你 的函数可能会永不停息的在那里递归调用了。

2016/3/18

25

汉诺(hanoi)塔问题--递归的经典问题
在世界刚被创建的时候有一座钻石宝塔(塔A),其 上有64个金碟。所有碟子按从大到小的次序从塔底堆放 至塔顶。紧挨着这座塔有另外两个钻石宝塔(塔B和塔 C)。从世界创始之日起,婆罗门的牧师们就一直在试 图把塔A上的碟子移动到塔C上去,其间借助于塔B的帮 助。每次只能移动一个碟子,任何时候都不能把一个碟 子放在比它小的碟子上面。有预言说,这件事完成时宇 宙会在一瞬间闪电式毁灭. 按1秒钟挪动一块计算,要把64块黄金圆盘挪动完, 要用5800亿年时间,而现在宇宙的年龄只有大约150亿年。

2016/3/18

26

2016/3/18

27

汉诺塔问题的递归求解
算法分析:当盘子比较多的时,问题比较复杂,所以我们先分析简单的情况: 如果只有一个盘子,只需一步,直接把它从A柱移动到C柱; 如果是二个盘子,共需要移动3步: (1) 把A柱上的小盘子移动到B柱; (2) 把A柱上的大盘子移动到C柱; (3) 把B柱上的小盘子移动到C柱; 如果N比较大时,需要很多步才能完成,我们先考虑是否能把复杂的移动过程 转化为简单的移动过程,如果要把A柱上最大的盘子移动到C柱上去,必须先把上 面的N-1个盘子从A柱移动到B柱上暂存,按这种思路,就可以把N个盘子的移动过 程分作3大步: (1) 把A柱上面的N-1个盘子移动到B柱; (2) 把A柱上剩下的一个盘子移动到C柱; (3) 把B柱上面的N-1个盘子移动到C柱; 其中N-1个盘子的移动过程又可按同样的方法分为三大步,这样就把移动过程 转化为一个递归的过程,直到最后只剩下一个盘子,按照移动一个盘子的方法移动 ,递归结束。

2016/3/18

28

#include<stdio.h> void move(char x, int n, char z) { // 第n个圆盘从塔座x搬到塔座z printf("将%d号盘从%c移到%c\n", n, x, z);

}
void hanoi(int n, char a, char b, char c) // 算法3.5 { // 将塔座a上按直径由小到大且自上而下编号为1至n的n个圆盘 // 按规则搬到塔座c上。b可用作辅助塔座 if (n == 1) // (出口) move(a, 1, c); // 将编号为1的圆盘从a移到c else { hanoi(n-1, a, c, b); // 将a上n-1个圆盘移到b,c作辅助塔(降阶递归调用) move(a, n, c); } } int main() // 将编号为n的圆盘从a移到c hanoi(n-1, b, a, c); // 将b上n-1个圆盘移到c,a作辅助塔(降阶递归调用)

{
int n; printf("3个塔座为a、b、c,圆盘最初在a座,借助b座移到c座。\n请输入圆盘数:"); scanf("%d", &n); hanoi(n, 'a', 'b', 'c'); } 2016/3/18
29

总结
?

递归算法解决问题的思路:

把规模较大的问题转化为性质相同规模较小的问题, 一直转化下去,因为问题的复杂程度常与规模有关, 当问题的规模小到一定程度时就很容易得到解,规 模较小的问题有解了,再利用这个解得到规模稍大 的问题的解,一直回归直到原问题的解。
?C语言中利用递归函数优雅的实现了递归算法。

2016/3/18

30


推荐相关:

递归调用详解,分析递归调用的详细过程

二、递归 递归,是函数实现的一个很重要的环节,很多程序中都或多或少的使用了 递归函数递归的意思就是函数自己调用自己本身,或者在自己函数调用的下级 函数中...


函数递归调用讲解

函数递归调用讲解一、函数调用与返回流程: 在一个函数中调用另一个函数时,程序控制即转入到被调用的函数中,在函 数代码执行完成后,返回到主函数调用处继续...


函数答案 (2)

30.以下 C 语言中,对函数不正确的描述是 D D A) 当用数组名作形参时,形参数组改变可使实参数组随之改变 B) 允许函数递归调用 C) 函数形参的作用范围只是...


实验五.函数文件的编写

函数文件: 命令文件: 命令窗口: 5、先用函数的递归调用定义一个函数文件求 ? i m ,然后调用该函数文件求 i ?1 n 50 10 1 k ? ?k2 ? ? 。 ? k ?...


C实验1-参考答案

进一步掌握函数的定义、调用、返回值以及值传递、地址传递的不同; 2、理解并掌握函数的嵌套调用和函数的递归调用; 3、了解全局变量和局部变量、动态变量、静态变量...


实验7 函数

? ? ? 掌握函数声明、定义和使用的方法; 掌握函数递归调用的方法; 掌握全局变量、局部变量、静态局部变量的概念和使用方法; 掌握定义头文件的方法,学会建立和调试...


C语言 函数

Eg5-3: 利用函数的递归调用实现某数的阶乘(函数递归调用) (1)源程序: #include <stdio.h> int fac(int n) { //求阶乘函数 3 int f; if(n<0) ...


1440112144_陈业鑫_lab09

三、实验目的: 1、熟悉函数的嵌套调用; 2、熟悉函数的递归调用,能根据具体情况编写递归函数。 3、能正确区分局部变量和全局变量的定义、作用域的不同,并能正确...


c语言实验报告9 函数的嵌套调用和递归调用、数组作为函数参数

1 台 班级: 姓名: 学号: 实验日期:2011 年 3 月 1 日 实验项目名称 实验目的 函数的嵌套调用和递归调用、数组作为函数参数 掌握函数的嵌套调用和递归调用。数...


浅析C语言递归算法

所谓递归 递归,简而言问。在函数中直接调用函数本身,称为直接递归调用。在函数中调用 递归 其它函数,其它函数又调用原函数,这就构成了函数自身的间接调用,称为间接...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com