5.1.2递归 课件(共19张PPT)-高中信息技术粤教版（2019）选择性必修1

(课件网) 递归 1 递归的概念 3 递归算法的设计方法 递归 2 递归算法的执行过程 递 归 （把问题不断分解为可操作性的小问题） （把小问题的结果返回给大问题，达到最终目的） 递归 终结条件 大问题的解决中嵌套着与原问题相似的规模较小的问题，这种问题的解决方法在计算机科学中称为递归，它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 递归的概念 阶乘的定义：一个正整数的阶乘是所有小于及等于该数的正整数的乘积。 递归算法的执行过程———求阶乘 n！= n*（n-1）！ n ！= n *（n-1）*…*2*1 （n-1）！= （n-1）*…*2*1 递归规律 1 （n=1） f（n）= n*f（n-1 ）（ n>1 ） def f (n): if n == 1: return 1 else: return n* f（n-1 ） print(f(5)) f（5）=5*f （4） f（4）=4*f （3） 递推 f（3）=3*f （2） 递推 f（2）=2*f （1） 递推 f（1）=1 递推 5！=？ 回归：1 1 回归：2 2 回归：6 6 回归：24 24 def f (n): if n == 1: return 1 else: return n* f（n-1 ） print(f(5)) 5！=120 递归=递推+回归 递归算法的执行过程———求阶乘 操作演示 递归算法的设计方法 把原问题分解成若干个相对简单且类型相同的小问题，这样复杂的原问题就变成相对简单的子问题，而简单到一定程度的子问题可以直接求解，最终原问题就可以通过递推得到解答。 设计方法 1.能够归纳出恰当的递归公式。 2.必须要有一个明确的递归终止条件。 探究活动———求解斐波那契数列 一对刚出生的小兔子，一个月后就能成长为成年兔，再过一个月后(即第三个月起)就每月生一对兔子。新生的兔子也按这个规律繁殖。 现在仅有一对刚出生的小兔子，问在没有兔子死亡的情况下，一年后总共繁殖成多少对兔子。 意大利数学家斐波那契 分析表 一月 二月 三月 四月 五月 1对 2对 3对 5对 1对 分 析 表 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月 小兔 1 1 1 2 3 5 8 13 21 34 55 大兔 1 1 2 3 5 8 13 21 34 55 89 合计 1 1 2 3 5 8 13 21 34 55 89 144 + = + = + = + = + = + = + = + = + = + = 数列规律：从第三项开始,后面的数总是前两数之和 数列规律：从第三项开始,后面的数总是前两数之和 递归终结条件 def f(n)： if n == 1 or n == 2: return 1 else: return f(n-1) + f(n-2) print(f(12)) 分 析 表 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月 小兔 1 1 1 2 3 5 8 13 21 34 55 大兔 1 1 2 3 5 8 13 21 34 55 89 合计 1 1 2 3 5 8 13 21 34 55 89 144 + = 1 n=1 1 n=2 f(n-1) + f(n-2) n>2 f(n)= 递归公式 def f(n)： if n == 1 or n == 2: return 1 else: return f(n-1) + f(n-2) print(f(5)) 斐波那契数列求解的执行过程 主程序f(5) 函数f(4) 函数f(3) 函数f(3) 函数f(2) =1 函数f(2) =1 函数f(1)=1 函数f(2)=1 函数f(1)=1 操作演示 知识拓展———斐波那契数列螺旋线 斐波那契螺旋线也称为“黄金螺旋线”，是以斐波那契数列数字为半径，连续绘制圆弧得到的螺旋线。 知识拓展———斐波那契数列螺旋线 课堂小结 递归 递归的概念 把问题转化为规模较小的同类子问题，通过函数自己调用自己来实现。 递归算法 的执行过程 递归算法 的设计方法 先传递，再回归 1.能够归纳出恰当的递归公式。 2.必须要有一个明确的递归终结条件 谢谢 ... ...