第四十七课 递归函数分析

递归的数学思想

递归是一种数学上分而自治的思想
递归需要有边界条件
当边界条件不满足时，递归继续进行
当边界条件满足时，递归停止
递归将大型复杂问题转化为原问题相同但规模较小的问题进行处理。

递归函数

函数体内存可以调用自己
递归函数
函数体中存在自我调用的函数
递归函数是递归的数学思想在程序设计中的应用
递归函数必须有递归出口
函数的无限递归将导致程序栈溢出而崩溃

递归函数设计技巧

递归模型的一般表示法

递归函数设计示例一

用递归的方法编写函数求字符串长度

47-1 递归版strlen

递归函数设计示例二

斐波拉契数递归解法 1,1,2,3,5,8,13,21,34,…

47-2 斐波拉契数列

递归函数设计示例三

汉诺塔问题
将木块借助B柱由A柱移动到C柱
每次只能移动一个木块
只能出现小木块在大木块之上
汉诺塔问题分解
将n-1个木块借助C柱由A柱移动到B柱
将最底层的唯一木块直接移动到C柱
将n-1个木块借助A柱由B柱移动到C柱

47-3 汉诺塔问题求解
小结
递归是一种将问题分而自治的思想
用递归解决问题首先要建立递归的模型
递归解法必须要有边界条件，否则无解