函数的递归调用

函数的递归调用

1.1 故事引入：从前有个山…

1.2 思考

 1.2.1 这个过程如果没有结束的话，结果是什么？

 1.2.2 如果该过程有结束的话，是否应该存在结束条件？

2.1 什么是函数的递归调用？

在调用一个函数的过程中出现了间接或直接地调用该函数本身，称为函数的递归调用。（函数体内调用了该函数本身）

2.2 应用场景

 2.2.1 求阶乘

 已知

• 1! = 1
• 0! = 1
• n! = n(n-1)! （n>1）

思考递归过程及其终止条件

 2.2.2 求斐波那契数列

 已知

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) （n ≥ 2，n ∈ N*）

思考递归过程及其终止条件

2.3 实现

阶乘实现：
我们使用函数F(n)来表示n!，则可以实现第一步：
定义一个函数F，其输入和输出均为整数：

	int F(int n){
		
	}
1
2
3

且已知 0! = 1 和 1! = 1
那么可得F(0)和F(1)的值均为1
那么有：

	int F(int n){
		if(0==n)return 1;
		if(1==n)return 1;
	}
1
2
3
4

但存在n不为0或1的时候，此时对公式2.2.1分析可得：
F(n) = n*F(n-1) （n>1）,当n大于1时n!为F(n),那么(n-1)!为F(n-1),于是可得：

	int F(int n){
		if(0==n)return 1;
		if(1==n)return 1;
		return n * F(n-1);
	}
1
2
3
4
5

3.1 运行并分析

3.1.1 运行结果

3.1.2 分析

F(4)怎么得到的？

4.1 总结

 4.1.1 回归故事：从前有个山…

 4.1.2 注意事项：

  a. 子问题须与原始问题为同样的事，且更为简单；

  b. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

4.2 作业

 4.2.1 复现求阶乘的代码

 4.2.2 根据前面的分析实现斐波那契数列

 4.2.3 如果不使用函数的递归调用是否可以解决上述两个问题