第二单元 微项目5 用递归算法优化程序 课件-2022-2023学年泰山版（2019）初中信息技术第二册

hthon:编程---5递归算法 微项目5 用递归算法优化程序 学习目标学习活过程与目标核心问题 1、跟踪递归的运行过程，通过数据跟踪实验，了解递归思想 的基本思路和运行过程，如何将大问题拆解为同类的小问题 2、探究递归算法的优势，通过案例对比递归与选代算法的不 同，探究递归算法的优势，递归的优势是什么 汉诺塔问题 用递归策略编程 汉诺塔(Hanoi Tower)是根据印度古老传说形成的 一个问题： 有A、B、c三根柱子，A柱上有n个穿孔圆盘(n>1), 盘的尺寸由下到上依次变小，要求把所有的圆盘移动 到c柱。 游戏规定，可以将圆盘临时放在柱，但大盘不 能叠在小盘上面，并且每次只能移动一个圆盘。 A B C 1 2 245 #/usr/bin/env python3#汉诺塔递归求解函数 def hanoi(n,begin,temp,end): if n==1: 捂 终 特打印圆盘移动信息 print(移动”，begin,"->",end) else: #完成挑钻战只需三步 hanoi(n-1,begin,end,temp) hanoi(1,begin,temp,end) hanoi(n-1,temp,begin,end) 龙、 #函数调用示例 n=5 print(“-汉诺塔”，n“层挑战操作步骤-”) hanoi (n,"A","B","C") 递归算法的条件 递归算法解决问题的核心：递归函数的构建。程序运 行时，由于递归函数不断调用自身，如果没有设置终止条 件，递归调用会形成限循环。 f条件表达式： #终止条件 语句 return值（或表达式） #可省略 else: 递归条件 包含自身函数名([参数列表)的语句 活动1跟踪递归的运行过程 递归过程： 下面通过一个累乘过程的数据跟踪检测小实 验，来体会递归算法是如何工作的 解决问题： 假设一个自然数n,累乘是将从1到n的所 有自然数相乘，乘积m=1x2x3x4x5x.xn。 递归只需少量的程序就可描述出解题过程所 递露蕻族大重菊调囷因减变宝我码的 算季李瑰 尚的屋9万汽云 的函致)。 日常生活中，以相似方法重复事物的现象被 称作递归（如照镜子），而在计算机领域，递归是 程序调用自身的编程技巧： 列如n=7m=1x2x3x4x5x.xn 递归的实现过程 当前n=7 当前n=6 r当前n=5 当前n=4 当前n=3 7! 6! 当前n￥2 3:1 ★当前n=1 当的乘积：2 当前乘积：6 当前乘积：24 当前乘积：120 当前乘积：720 当的乘积：5040 m=5040 那乘运行结果 递归算去的程序买现 #!/usr/bin/env python3 当前n=7 当前n=6 def fact(n): #自定义函数 当前n=5 print("当前n=”,n 跟踪显示n,可省略 当前n=4 if n==1: 终止条件 当前n=3 结束递归 当前n=2 累乘运行结果 return 1 当前n=1 else: 递归条件 f=n*fact(n-1) 调用递归 当前乘积：2 跟踪显示累乘的积 当前乘积：6 print("当前乘积："，f) return f返回乘积 当前乘积：24 当前乘积 :120 #主程序 当前乘积：720 当前乘积： print("m=",fact(7)) 调用递归 5040