5.5递归算法实例及程序实现

1 递归算法实例及程序实现递归算法实例及程序实现 班级 班级 姓名 姓名 递归算法的含义递归算法的含义 递归算法是把规模较大的问题逐步化解为规模较小的问题的算法 以及当问题的规模递归算法是把规模较大的问题逐步化解为规模较小的问题的算法 以及当问题的规模 小到某种程序时 问题的解是什么 这时 问题的解是已知的或者它能相当容易地计算出小到某种程序时 问题的解是什么 这时 问题的解是已知的或者它能相当容易地计算出 来 来 而计算过程中递归的展开与递归的返回则是由计算机自动地进行 递归调用是函数体 而计算过程中递归的展开与递归的返回则是由计算机自动地进行 递归调用是函数体 或过程体中出现调用其自身的语句 或过程体中出现调用其自身的语句 递归算法的优点和缺点递归算法的优点和缺点 优点 编写简单 可读性强优点 编写简单 可读性强 缺点 不能保证速度和效率 可能会导致耗尽内存空间 引起程序出错缺点 不能保证速度和效率 可能会导致耗尽内存空间 引起程序出错 实例实例 1 计算计算 n 的阶乘的阶乘 将下列程序段补充完整 将下列程序段补充完整 Function f n As Integer As Long If n 1 Then 1 Else 2 End If End Function Private Sub Command1 Click Dim n As Integer Dim nk As Long n Val Text1 Text nk f n Text2 Text Str nk End Sub 思考 如果不用递归算法 用传统的算法 又该如何实现呢 思考 如果不用递归算法 用传统的算法 又该如何实现呢 For 语句 语句 S 1 For i n to 1 Step 1 S S i Next i Print S Do 语句 语句 S 1 3 Do While 4 S S i 5 Loop Print S 实例实例 2 兔子数列问题兔子数列问题 2 月份月份1234567891011 对数对数1123581321345589 Function f n As Integer As Long If n 1 Or n 2 Then 6 Else 7 End If End Function 思考 如果不用递归算法 用传统的算法 又该如何实现呢 思考 如果不用递归算法 用传统的算法 又该如何实现呢 For 语句 语句 Private Sub Command1 Click Dim n As Integer i As Integer Dim a 1 To 100 As Long n Val Text1 Text a 1 1 a 2 1 For i 3 To n a i a i 1 a i 2 Next i Text2 Text Str a n End Sub Do 语句 语句 Private Sub Command1 Click Dim n As Integer i As Integer Dim a 1 To 100 As Long n Val Text1 Text a 1 1 a 2 1 8 Do While i n 9 10 11 Text2 Text Str a n End Sub 实例实例 3 求平方和求平方和 Private Sub Command1 Click Dim n As Integer i As Integer Dim s As Long n Val Text1 Text For i 1 To n 12 Next i Text2 Text Str s End Sub Function f ByVal n As Integer As Long If n 1 Then 13 Else 14 End If End Function 实例实例 4 求数列和求数列和 Private Sub Command1 Click Dim n As Integer i As Integer Dim s As 15 n Val Text1 Text For i 1 To n 16 Next i Text2 Text Str s End Sub Function f ByVal n As Integer As Single If n 1 Then 17 Else 18 End If End Function 实例实例 5 十进制数转二进制数十进制数转二进制数 222 21nS n S n 2 1 1 8 1 6 1 4 1 2 1 3 Dim n As Integer r As Integer s As String n Val Text1 Text Do While n 0 19 20 s CStr r s Loop Text2 Text s Function DtoB x As Integer As Long If x 0 Then DtoB 21 Else DtoB 22 End If End Function 实例实例 6 小猴吃桃问题小猴吃桃问题 Dim days As Integer i As Integer Dim s As Integer a 10 As Integer a 10 1 days Val Text1 Text For i 10 To 1 Step 1 a i 1 a i 1 2 Next i Text2 Text Str a days Function tao days As Integer As Integer If days 10 Then tao 1 Else 23 End If End Function 实例实例 7 求最大公约数求最大公约数 Private Sub Command1 Click Dim x As Integer 第一个整数第一个整数 Dim y As Integer 第二个整数第二个整数 Dim r As Integer Dim s As Integer 最大公约数最大公约数 x Val Text1 Text y Val Text1 Text r x Mod y Do While r 0 24 25 26 Loop s y Text3 Text Str s End Sub Function gcd x As Integer y As Integer As Integer If y 0 Then gcd x Else 27 End If End Function Private Sub Command1 Click Dim A As Integer B As Integer Dim gys As Long A Val Text1 Text B Val Text2 Text 28 Text3 Text Str gys End Sub 实例实例 8 汉诺塔问题汉诺塔问题 问题描述 有问题描述 有 n 张圆盘 依半径大小自下而张圆盘 依半径大小自下而 上 半径从大到小 套在上 半径从大到小 套在 a 柱上 柱上 b 柱和柱和 c 柱开始时无圆盘 每次只允许移动最上面一柱开始时无圆盘 每次只允许移动最上面一 张圆盘到另外的柱子上去 但绝不允许发生张圆盘到另外的柱子上去 但绝不允许发生 柱子上出现大盘子在上 小盘子在下的情况 柱子上出现大盘子在上 小盘子在下的情况 请你设计将请你设计将 a 柱上的柱上的 n 张搬移到张搬移到 c 柱的方法 柱的方法 4 设计方法 那么运用递归的思想可知 若想将设计方法 那么运用递归的思想可知 若想将 n 号盘放到号盘放到 c 柱上 那么必须先把柱上 那么必须先把 1 n 1 号盘移动到 号盘移动到 b 柱上 此时柱上 此时 c 柱作为辅助轴 即柱作为辅助轴 即 hanoi n 1 a b c 然后移动 然后移动 n 号盘到号盘到 c 柱上 即柱上 即 move a n c 最后将 最后将 b 柱上的 柱上的 1 n 1 号盘移动到 号盘移动到 c 柱上 此柱上 此 时时 a 柱作为辅助轴 即柱作为辅助轴 即 hanoi n 1 b c a 当 当 n 1 时返回主函数时返回主函数 hanoi n a c b 汉诺塔问题汉诺塔问题 每一步移动的方法都是固每一步移动的方法都是固 定的 我们用定的 我们用 f n 代表代表 n 个圆盘移动的次数 个圆盘移动的次数 f n 1 代表代表 n 1 个圆盘移动的次数 则会有如个圆盘移动的次数 则会有如 下表达式 下表达式 f n f n 1 2 1 其中 其中 f n 2 n 1 例如当 例如当 n 2 时 时 f n 3 当 当 n 4 时 时 f n 15 当 当 n 14 时 时 f n 16383 Dim num As Long Sub hanoi n As Integer a As String c As String b As String Hanoi 过程四个参数分别是过程四个参数分别是 N 个个 盘数 源柱 目标柱 帮助柱 过程的意思是将盘数 源柱 目标柱 帮助柱 过程的意思是将 N 个盘从源柱搬动到目标柱通过帮助柱帮个盘从源柱搬动到目标柱通过帮助柱帮 助下 助下 If n 1 Then 当只有一个盘时当只有一个盘时 num num 1 List1 AddItem Str num a c 搬动一个盘从源柱到目标柱搬动一个盘从源柱到目标柱 Else 29 搬动搬动 N 1 个盘从个盘从 A 柱到柱到 B 柱 在柱 在 C 柱帮助柱帮助 下下 num num 1 List1 AddItem Str num a c 30 搬动搬动 N 1 个盘从个盘从 B 柱到柱到 C 柱 在柱 在 A 柱帮助柱帮助 下下 End If End Sub Private Sub Command1 Click Dim n As Integer n Val Text1 Text Call hanoi n A C B 将将 N 个盘从源柱个盘从源柱 A 柱搬动到目标柱柱搬动到目标柱 C 柱在帮助柱柱在帮助柱 B 柱帮助下柱帮助下 List1 AddItem 共共 Str num 次次 End Sub Private Sub Text1 Click num 0 List1 Clear Text1 Text End Sub 教师点拨教师点拨 递归算法 程序调用自身的编程技巧 是把问题转化为规模缩小了的同类问题的子问递归算法 程序调用自身的编程技巧 是把问题转化为规模缩小了的同类问题的子问 题 然后调用自身的函数 或过程 来表示问题的解 题 然后调用自身的函数 或过程 来表示问题的解 递归算法的特点 递归算法的特点 递归就是直接或间接调用自身 递归就是直接或间接调用自身 在使用递归策略时 必须有一在使用递归策略时 必须有一 5 个明确的递归结束条件 称为递归出口 边界 个明确的递归结束条件 称为递归出口 边界 参考答案 参考答案 1 f 1 11 Loop 21 0 2 f n f n 1 12 s s i 2 或或 s s i i 22 DtoB x 2 10 x mod 2 3 i n 13 f 1 23 tao tao days 1 1 2 4 i 1 14 f n n f n 1 或或 f n 2 f n 1 24 x y 5 i i 1 15 Double 25 y r 6 f 1 16 s s 1 i 2 i 26 r x mod y 7 f f n 1 f n 2 17 f 0 5 27 gcd gcd y x mod y 8 i 3 18 f 1 n 2 n f n 1 28 gys gcd A B 9 a i a i 1 a i 2 19 r n mod 2 29 Call hanoi n 1 a b c 10 i i 1 20 n n 2 30 Call hanoi n 1 b c a 参考答案 参考答案 1 f 1 11 Loop 21 0 2 f n f n 1 12 s s i 2 或或 s s i i 22 DtoB x 2 10 x mod 2 3 i n 13 f 1 23 tao tao days 1 1 2 4 i 1 14 f n n f n 1 或或 f n 2 f n 1 24 x y 5 i i 1 15 Double 25 y r 6 f 1 16 s s 1 i 2 i 26 r x mod y 7 f f n 1 f n 2 17 f 0 5 27 gcd gcd y x mod y 8 i 3 18 f 1 n 2 n f n 1 28 gys gcd A B 9 a i a i 1 a i 2 19 r n mod 2 29 Call hanoi n 1 a b c 10 i i 1 20 n n 2 30 Call hanoi n 1 b c a 参考答案 参考答案 1 f 1 11 Loop 21 0 2 f n f n 1 12 s s i 2 或或 s s i i 22 DtoB x 2 10 x mod 2 3 i n 13 f 1 23 tao tao days 1 1 2