C Programming in Action

Presentation on theme: "C Programming in Action"— Presentation transcript:

1 C Programming in Action
实战2 递归 递归思想 张修军 Chengdu university

2 项目需求知识点 递归算法设计，就是把一个大型复杂的问题层层转化为 一个与原问题相似的规模较小的问题，在逐步求解小问 题后，再返回（回溯）得到大问题的解。 递归算法设计的关键在于找出递归关系（方程）和递归 终止（边界）条件。

3 项目需求知识点 n!阶乘问题 定义：n!=n*(n-1)*(n-2)*…*2*1 n!=n*(n-1)!
1!=1*0! 0!=1 递归定义：n!=n*(n-1)! 且 0!=1

4 项目需求知识点 n!阶乘问题 命名 n!的计算函数为int fac(int n)-----factorial阶乘
则(n-1)!的调用函数就是fac(n-1) 递推关系就是 fac(n)=n*fac(n-1) 边界条件就是：fac(0)返回值为1

5 项目需求知识点

6 项目需求知识点 代码演示 #include "stdio.h" int fac(int n) { if (n==0) return 1; /*递归结束*/ if (n>=1) return n*fac(n-1); /*处理递归并返回结果*/ } void main() int i; printf("Please input n's value\n"); scanf("%d",&i); printf("%d!=%d\n",i,fac(i));

7 项目需求知识点 代码演示（方便debug看出调用关系） #include "stdio.h" int fac(int n) {
int j; if (n==0) j = 1; /*递归结束*/ if (n>=1) j = n*fac(n-1); /*处理递归并返回结果*/ return j; } void main() int i; printf("Please input n's value\n"); scanf("%d",&i); printf("%d!=%d\n",i,fac(i));

8 项目需求知识点 斐波那契数列(Fibonacci numbers) f0=0,f1=1,f2=1,f3=2,f4=3,f5=5..

9 项目需求知识点 代码演示 #include "stdio.h" int fib(int n) { if (n<=1)
return n; /*递归条件*/ if (n>1) return fib(n-1)+fib(n-2); /*递归*/ } void main() int i; printf("Please input fib's number\n"); scanf("%d",&i); printf("fib(%d)=%d\n",i,fib(i));

10 项目需求知识点 代码演示（方便debug看出调用关系） #include "stdio.h" int fib(int n) {
int j; if (n<=1) j = n; /*递归条件*/ if (n>1) j = fib(n-1)+fib(n-2); /*递归*/ return j; } void main() int i; printf("Please input fib's number\n"); scanf("%d",&i); printf("fib(%d)=%d\n",i,fib(i));

11 项目需求知识点 f(3)=f(2)+f(1) f(2)=f(1)+f(0)
f(3)->f(2)->f(1),f(0)->f(2)->f(1)-f(3) 则局部变量n的变化规律为 3->2->1->0->2->1->3

12 Thanks C语言综合项目实践 在 “幻灯片放映”模式，单击箭头进入 PowerPoint 入门中心。 成都大学信息科学与技术学院