选修1 算法与程序设计《第3章 常用算法及程序实现 第四节 递归法 活动 用递归法求解“兔子问题”》优秀教案

选修1 算法与程序设计《第3章 常用算法及程序实现 第四节 递归法 活动 用递归法求解“兔子问题”》优秀教案

递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了调用它自身的情况。递归是利用系统的堆栈保存函数当中的局部变量来解决问题的，因为函数调用的开销，递归常常会带来效率问题。本节课不仅要学会用递归法解决问题，更重要的是领会递归思想的精髓。递归思想是计算机学科中的核心技术思想之一，其本质反映的是一种将复杂问题简单化的思维方法。

三、学习目标

理解递归的含义，能找出递归问题中缩小问题规模的递归处理方法及递归结束条件，了解递归算法的优缺点；

能用程序实现递归算法，学会用简单模式解决复杂问题的方法；

领悟递归思想，体验递归思想在生活实际中的应用。

四、教学重难点

教学重点：分析递归结束条件及缩小问题规模的方法，递归算法的程序实现

教学难点：递归算法的程序实现

五、教学策略

呈现斐波那契数列问题，由学生比较熟悉的递推法入手，针对问题描述中的不严谨之处，引入递归定义及其关键因素——递归结束条件和缩小问题规模的递归处理。在递归的学习过程中，学生通过阅读代码、尝试模仿、归纳提炼、拓展应用等环节逐渐完成知识的内化并达到应用、迁移的目的。最后通过实践比较，让学生体验递推、递归两种方法的运行效率，并分析造成递归法运行效率低下的原因，学会辩证的看待问题。让学生在应用递归思想时逐渐形成一个意识——学习程序设计不仅仅是为了编程解决问题，更重要的是形成正确的解决问题的方法和态度。

六、教学过程

（一）呈现问题，初识递归

某电子购物平台15周年庆，特别推出了签到送积分活动。活动具体规则如下：从6月1日到6月15日，第1天、第2天签到均可领取1个积分，第3天签到可领取2个积分，第4天签到可领取3个积分，第5天签到可领取5个积分，……请问，小丽从6月1日起就坚持每天签到，那么6月15日那天她将领到多少积分？你能找出这15天每天所领积分间的关系吗？

?

图1?积分领取情况

观察图1，我们发现：第1天和第2天都只有1个积分，从第3天到第15天，每天领取的积分数就进入了一个重复的计算过程，也即每天领取的积分是前两天的积分之和。为了存放每天领取的积分数，我们可以定义一个数组Fib(15)，该数组中，Fib(1)=1，Fib(2)=1，而从第3天开始的重复过程，可以利用循环来完成。代码如下：

Dim Fib(15) As Integer

Fib(1) = 1

Fib(2) = 1

For i = 3 To 15

????Fib(i) = Fib(i - 1) + Fib(i - 2)

Next i

Print Fib(15)

刚才我们计算的这一组数：1、1、2、3、5……是一个典型的斐波拉契数列，在解决这个问题的过程中，借助数组，从已知条件出发，利用循环的方式按照一定规则从前往后递推，最后得出了结论，这种解决问题的方式我们称之为递推法。然而在描述这组数时我们使用了“……”，在数学里经常看到这种写法，实际上这种写法并不科学，是数学表述中常见的不精确性。因为它的意义依赖于人对省略号的理解和共识。所以，斐波拉契数列还可以这样定义：

这种定义方式将问题分成了两种情况，其中一种可以直接求出结果；另一种是把问题分解成规模更小、与原问题相同解法的小问题。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，我们称之为递归法。递归通常使用自定义函数的形式来实现，如此，求斐波那契数列就变成了一件极简单的事情：