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


推荐相关:

函数递归调用求阶乘

函数递归调用求阶乘_计算机软件及应用_IT/计算机_专业资料。#include<stdio.h> double fun(int n); main() { int a; double b; printf("请输入要求几的...


函数的嵌套调用和递归调用

实验目的 1) 熟悉定义函数的方法,函数实参与形参 的对应关系以及“值传递”的方式; 2) 熟悉函数的嵌套调用和递归调用的方法; 3) 熟悉全局变量,局部变量概念和...


深入理解递归函数

深入理解递归函数_数学_自然科学_专业资料。深入理解递归函数的问题,透彻 深入理解递归函数刚开始接触编程对递归调用都是比较头痛,很多年前我也会一样。昨天晚上睡觉...


调用递归过程或函数时,处理参数及返回地址需要用一种称...

函数调用过程中形成嵌套时,则应使最后被调用的函数最先返回,递归函数执行时也是如此。例如,用递归方式求4的阶乘(以factorial(n)表示求n的阶乘)的过程如下所示:...


递归调用教学设计

《C 语言——递归调用》教学设计 教学目标及依据:根据教学大纲和本节学习重点,结合学生知识现状, 使学生学会使用和设计递归函数 去解决较复杂的问题。 教学重点难点...


...程序中各函数之间( )。 A.既允许直接递归调用也允许...

正确答案 A 解析 [解析] 本题考查函数调用的基本概念。在函数调用时,只要符合函数的使用,程序中的各个函数间既可以直接调用其他函数,也可以递归调用其自身。最新...


函数测试题

被调用时才分配内存单元 23、以下关于函数递归调用说法中错误的是( ) A、递归调用时,调用函数又是被调用函数,即递归函数将反复调用其自身 B、为了防止递归调用无...


C语言中函数嵌套调用和递归调用

C语言中函数嵌套调用和递归调用_电子/电路_工程科技_专业资料。函数嵌套与递归调用的区别函数嵌套是语言特性,递归调用是逻辑思想。 1 函数嵌套函数嵌套允许在一个函数...


递归原理讲解

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


函数的递归调用是指 A.函数的自我调用B.函数的嵌套调用...

函数的递归调用是指 A.函数的自我调用B.函数的嵌套调用C.主函数调用系统函数 D.系统函数调用主函数正确答案及相关解析 正确答案 A 解析 暂无解析 ...

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