工信版（中职）Python编程基础与应用电子课件函数的递归

YCF （中职）Python编程基础与应用电子课件函数的递归 1 函数的递归 主讲： 朱海鑫 ： 《Python编程基础与应用》配套课件 2 + contents 目 录 什么是函数的递归 递归范例 阅读角 《Python编程基础与应用》配套课件 3 函数的递归 01 《Python编程基础与应用》配套课件 4 什么叫递归函数？ 什么叫递归函数？简而言之，函数的递归就是在函数的定义中，函数内部的语句调用函数本身。 举个例子，我们来计算非负整数的阶乘n! = 1 x 2 x 3 x ... x n。简单分析一下： n!=1 #当n=1 n!=1x2=2 #当n=2 n!=1x2 x3 =6 #当n=3 n!=n x(n-1)! #当n>1时 用函数f(n)表示，可以看出： f(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = f(n-1) x n 所以，f(n)可以表示为n x f(n-1)，只有当n=1时需要特殊处理，其它情况就是n!=n x(n-1)!运算。 《Python编程基础与应用》配套课件 5 递归范例 02 《Python编程基础与应用》配套课件 6 范例6-14：非负整数的阶乘n! #定义 def factorial(n): if n==1: return 1 else: return n * factorial(n - 1) #调用 for i in (range(1,10)): print(i,"!=",factorial(i)) 它的运行结果如下： 1 != 1 2 != 2 3 != 6 4 != 24 5 != 120 6 != 720 7 != 5040 8 != 40320 9 != 362880 《Python编程基础与应用》配套课件 7 阅读角 03 《Python编程基础与应用》配套课件 8 汉诺塔问题 汉诺塔问题就是递归问题的一个经典案例。 汉诺塔问题源于印度一个古老传说。相传大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘，如图所示。问应该如何操作？ 《Python编程基础与应用》配套课件 9 汉诺塔问题 汉诺塔问题的解决思路：我们可以先假设除a柱最下面的盘子之外，已经成功地将a柱上面的63个盘子移到了b柱，这时我们只要再将最下面的盘子由a柱移动到c柱即可。 当我们将最大的盘子由a柱移到c柱后，b柱上便是余下的63个盘子，a柱为空。因此现在的目标就变成了将这63个盘子由b柱移到c柱。这个问题和原来的问题完全一样，只是由a柱换为了b柱，规模由64变为了63。因此可以采用相同的方法，先将上面的62个盘子由b柱移到a柱，再将最下面的盘子移到c柱。 以此内推，再以b柱为辅助，将a柱上面的62个圆盘最上面的61个圆盘移动到b柱，并将最后一块圆盘移到c柱。 我们已经发现规律，我们每次都是以a或b中一根柱子为辅助，然后先将除了最下面的圆盘之外的其他圆盘移动到辅助柱子上，再将最底下的圆盘移到c柱子上，不断重复此过程。 这个反复移动圆盘的过程就是递归，例如我们每次想解决n个圆盘的移动问题，就要先解决（n-1)个盘子进行同样操作的问题。 《Python编程基础与应用》配套课件 10 感谢聆听 主讲： 朱海鑫 ： 《Python编程基础与应用》配套课件 11 $