§5·5妙趣横生的算法－递归
★ 教学目标
知识与技能：
1、 理解什么是递归算法，用递归算法的思想分析问题 2、 能够应用自定义函数方法实现递归算法的编程
过程与方法：参与讨论，通过思考、动手操作，体验递归算法的方法
情感态度与价值：结合实例，激发数学建模的意识，培养多维度思考问题和解决问题，激发审美情感。 ★ 重点与难点
重点：理解什么是递归算法，会用递归算法思想分析问题；应用自定义函数方法实现递归算法的编程
难点：应用自定义函数方法实现递归算法的编程
学习思维导图：
一、认识递归：
1、小游戏：报数
2、头脑风暴：举出你身边的递归的例子 二、新知导学：
问题：有甲、乙、丙、丁四人，从甲开始到丁（甲＞乙＞丙＞丁），一个比一个大1岁，已知丁10岁，问甲几岁？
1
1．分析问题：这是递归法的一道非常典型的题目——因为我们可以很显然知道：假设要计算甲的年龄，那么必须知道乙的年龄；同样，算乙的必须知道丙的，算丙的必须知道丁的，因为丁已知，自然可以往前推算了。现在假设有一个数学模型（函数）可以计算出他们各自的年龄（为方便我们给他们编号—甲＝1，乙＝2，丙＝3，丁＝4），那么存在一个F(X)函数，X表示某人的编号，其规律如下：
F(1)=F(2)+1
F(2)=F(3)+1 F(3)=F(4)+1 F(4)=10
这种按同一方法把问题的计算规模逐步变小的过程叫做“递归的展开”，然后要逐级代入直到求出结果，这一过程称为递归的返回
F(4)=10
F(3)=F(4)+1=11 F(2)=F(3)+1=12 F(1)=F(2)+1=13
2、写出递归表达式：显然，当n=4时，问题的解为10，而当n<4时，问题的解可转换为：
F(n)=f(n＋1)+1
3、编写程序：递归算法通常用自定义函数来实现，称为递归函数，如以上题可以写成如下函数：
Function f(n as integer) as integer If n=4 then ＿＿＿ Else
＿＿＿＿＿ End if
End function 4、调试运行程序：
归结：解决递归问题的一般步骤：
1． 分析问题，写出递归与返回的过程
2． 建立数学模型（写出递归表达式）
X=D 返回某个常数作为结果
F（x）=
F（X’）……返回一个自身嵌套的表达式，自身调用，直到F（X”……）
＝D作为条件终止。
3． 编写自定义函数代码(一般形式为) Function f(n as ____ ) as ______ If＿＿＿＿then ＿＿＿＿ Else
＿＿＿＿＿
2
End if
End function 4． 调试运行程序
三、合作探究：小猴吃桃问题:
有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?
1．分组讨论，推算10天吃桃的过程
2、根据推算，得出的数据，填写下表：（建议先填写后四天，前六天通过调试程序，根据运行结果填写） 天数 桃子数 1 2 3 4 5 6 7 8 9 10 3、根据推算10天吃桃的数据和本题大意讨论并写出递归表达式： 假设第n天（n<10）的桃子数为tao(n)那么：
4、编写自定义函数程序：
Function tao(n as integer) as integer If n=10 then Tao=1 Else
____________ End if
End function
5、将以上程序应用到VB中，调试运行，观察运行结果是否正确。 6、将你的程序提交给老师 四、欣赏：递归之美
3
五、随堂练习：
1、数列1，4，7，10，13，……的递归表达式为（ ）
(A) f(n)=n+3 ；f(1)=1 (B) f(n)=n*2-1 ；f(1)=1 (C) f(n)=n*2+1 ；f(1)=1 (D) f(n)=f(n-1)+3 ；f(1)=1 2、 一个递归算法必须包括（ ）
( A) 递归部分 (B) 终止条件和递归部分 (C ) 循环部分 (D) 终止条件和循环部分
选择算法：我们在用计算机解决问题时，常采用的算法有解析法、穷举法、递归法、冒泡排序法、选择排序法等，分析下列问题应采用哪种算法解决？
3、走台阶问题。从楼下到楼上共有n个台阶，每一步有2种走法：走1个台阶；走2个台阶。走上这n个台阶共有多少种走法？（提示：有n级台阶时，走法有f(n-1)+f(n-2)种） ＿＿＿＿
4、用10元纸币（可取的面值有1元、2元或5元）组成一笔总值为24元的现金，设计一个算法输出所有不同的组成方法。
＿＿＿＿＿＿＿
5、信封问题，有N个信封，N封信，将N封信装入N个信封，全部都装错的方法有多少种数？
f(n)=(n-1)*(f(n-1)+f(n-2)) (n>2) f(1)=0 f(2)=1
＿＿＿＿＿＿＿＿＿
六、课堂小结：（及时总结、不断提高!）
七、课后作业：爱因斯坦的谜语
1、在一条街上，有5座房子，喷了5种颜色。 2、每个房里住着不同国籍的人
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物 问题是：谁养鱼？ 提示：
1、英国人住红色房子 9、 挪威人住第一间房 2、瑞典人养狗 10、抽Blends香烟的人住在养猫的人隔壁 3、丹麦人喝茶 11、养马的人住抽Dunhill 香烟的人隔壁 4、绿色房子在白色房子左面 12、抽Blue Master的人喝啤酒 5、绿色房子主人喝咖啡 13、德国人抽Prince香烟 6、抽Pall Mall 香烟的人养鸟 14、挪威人住蓝色房子隔壁 7、黄色房子主人抽Dunhill 香烟 15、抽Blends香烟的人有一个喝水的邻居 8、住在中间房子的人喝牛奶
4
因篇幅问题不能全部显示，请点此查看更多更全内容