资源简介

(共19张PPT)
递归
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.必须要有一个明确的递归终结条件
谢谢

展开更多......

收起↑