5.2迭代与递归　课件　2022—2023学年浙教版（2019）高中信息技术选修1

迭代算法与递归算法 选修一：数据结构 更多模板请关注：https://haosc.tukuppt.com 1 探究一：写一段程序实现求 n！ 迭代是重复反馈过程的活动，其目的通常是为了使结果符合目标要求 n=5 result=n #第一次迭代 result=n*4 #第二次迭代 result=n*3 #第三次迭代 result=n*2 #第四次迭代 result=n*1 #第五次迭代 迭代关系式 2 探究一：迭代的概念 迭代算法： ①重复反馈的过程 ②迭代过程：对迭代过程的重复 ③每一次迭代结果会被用来作为下一次迭代的初始值 3 探究一：迭代的概念 迭代算法解决问题过程： ①确定迭代变量。 迭代算法处理的问题时，由旧值递推出新值的变量称为迭代变量。 ②建立迭代关系式（数值关系）。 从变量的前一个值推出其下一个值的公式（或关系）。 ③控制迭代过程（结束条件）。 迭代过程在经过若干次重复执行以后要能结束，因此，要设定迭代结束的条件。 4 探究二：迭代算法求a的平方根 迭代算法： ①确定迭代变量 ②建立迭代关系式 ③控制迭代过程 迭代法求a的平方根： ①估计近似值x,令x等于x和a/x的平均数 ②x的值逼近于a的平方根，当误差小于时，将x的值作为a的平方根 5 探究二：迭代算法求a的平方根 迭代算法： ①确定迭代变量 ②建立迭代关系式 ③控制迭代过程 每次迭代结果将作为下一次迭代的初始值 6 1（n=1） n*fac(n-1)（n≠1） fac(n) 探究三：递归算法求 n！ 递归：大问题中嵌套小问题，通过调用自身，不断降低问题的规模，进而求解 n = 5 5！=5*4！ 4！=4*3！ 3！=3*2！ 2！=2*1！ 1 ！ = 1 递推：分解问题 回归：代值求解 7 fac(4) 4*fac(3) 第1次调用 第2次调用 3*fac(2) 第3次调用 2*fac(1) 第4次调用 1 返回值1 返回值1 返回值2 返回值6 探究三：递归过程 探究三：递归算法求 n！ 递归：大问题中嵌套小问题，通过调用自身，不断降低问题的规模，进而求解 1（n=1） n*fac(n-1)（n≠1） fac(n) 设计递归算法：确定递归公式和递归结束条件 9 探究四：如何用栈实现递归 1*fac(0) 2*fac(1) 3*fac(2) 4*f