“用递归算法解决问题”教学设计 第三章第五节

江苏省徐州市第三十六中学　陶　江　221008

一、教材分析

“用递归法解决问题”是《算法与程序设计》第三章第五节第二部分的内容，前面学习了“用解析法解决问题”、“用穷举法解决问题”、“在数组中查找数据”及“对数据进行排序”，“递归算法”的基本思想：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。

二、学情分析

教学对象是高中二年级学生，是高中所学的最后一个算法，之前学过了程序设计的各种语句，函数、算定义函数，还学习过了“解析法”、“穷举法”等算法。

三、教学目标

1．知识与技能：

(1) 理解什么是“递归算法”，能用“递归算法”的思想分析问题；

(2) 能够应用自定义函数方法实现“递归算法”的编程。

2．过程与方法：

学生参与讨论，通过游戏过程，思考“递归算法”思想，体验“递归算法”的程序。

3．情感态度与价值观：

(1) 通过游戏中的“坚持”一词，让学生感悟“再坚持一下”的含义；

(2) 结合数学中的实例，激发学生的数学建模意识，培养学生多维度的思考问题和解决问题。

四、教学重点、难点

1．教学重点：

理解什么是“递归算法”，能用“递归算法”的思想分析问题。

2．教学难点：

应用自定义函数方法实现“递归算法”的编程。

五、教学方法

任务驱动，小组讨论，讲授法

六、课程过程

1．课堂导入

师：今天我先给大家做个游戏，老师的纸上写了一个词(坚持，在上课之前事先告诉其中的一个同学)，我们班有一位同学知道写的是什么！但是他不能就这样告诉大家，有一个规则可以让我们知道内容？规则是：从第一排的第一个同学开始；每位同学只问他相邻的同学，每位同学最多只能被问一次，而且一个同学不能再问第二人，当任何一个同学知道了答案,要求立即告诉曾经问过他的那个同学，不能告诉其它同学，然后知道内容的同学，继续向前告之，以此类推；一直到第一个同学结束。

学生活动：按照游戏规则开展进行到最后。

师：请第一个同学说说是什么词？

老师展示纸上的内容(“坚持”)

师：“坚持”作为高中生的我们，每个人都对这个词感悟不同，我们生活中的任何事，都不是一帆风顺的，当遇到挫折，你是“放弃”，还是“再坚持一下”，通过自己的努力或者去寻求适当的帮助呢。在你遇到困难时，往往别人也同样感觉困难无比，“再坚持一下”，也许就会产生完全不同的结果。

2．交流探索

师：刚才的游戏，第一个同学想知道结果，就必须第二个同学知道，第二个同学想知道结果，就必须第三个同学知道，同理，一直往后进行；当有一个同学知道结果后，就逐级向前告知，一直返回到第一个同学，任务结束。这个过程就是我们今天要学习的递归算法的思想。

老师板书：递归法

师：刚才的游戏，如果想游戏结束，必须有个什么条件？

学生回答：必须有人知道纸上的内容。

师：用算法中专业的语言来说，就是必须有出口，否则就会像死循环那样，不停的算下去，最终造成死机。

师：递归法通常都是借助自定义函数来实现，函数是为了实现某种功能而编写的一段相对独立的程序，并且可以多次的调用。

老师投影：这个游戏的伪代码描述

function what(n)

if  我知道答案  then

我就告诉你

else

我要问下一位同学后再告诉你

endif

end function

3．解决问题

例题1：有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?(猴子摘桃)

师：以小组为单位，讨论此题应该如何解决？

学生口述此题的解决方法

建立数学模型：

师：假设第n天(n<10)的桃子数为taozi(n)，那么当n<10时，就有taozi(n)=？

生：(taozi(n+1)+1)*2

师：此题的出口是什么？

生：第10天的桃子数是1个。

幻灯片出示自定义函数taozi的代码：

Function taozi(ByVal n As Integer) As Integer

 If n=10 Then

    taozi=1

 Else

　  taozi=(taozi(n + 1)+1) * 2

 End If

End Function

例题2：求N！

师：求N的阶乘，这是数学里的一种术语。 此题的意思是：求从1乘以2乘以3乘以4一直乘到N。

建立数学模型：

师：假设N的阶乘为ji(n)，那么ji(n)=？

生：ji(n-1)*n

师：此题的出口是什么？

生：1的阶乘是1。

学生尝试进行编程

可能出现的问题是写成ji=ji(n+1)*n

师：谁来说说这两题在递归调用过程中的不同？

生：第一题出口是最后一天(第10天)，要想知道第n天的桃子数，就要知道第(n+1)天的。此题的出口是第一个数的，要想知道第n个数的阶乘，就要知道第(n-1)的数的阶乘。

幻灯片出示解决此题的程序：

Function ji(n As Integer) As Integer

 If n=1 Then

  ji=1

 Else

  ji=ji(n-1)*n

 End If

End Function

Private Sub Command1_Click()

Dim n As Integer

 n =val(InputBox("请输入n"))

 Print  ji(n)

End Sub

4．课堂小结

师：我们今天所学习的算法是“递归算法”，什么是递归算法，递归算法有什么特点。

师生讨论，共同小结：

(1)递归算法是数值层层调用实现的，函数先由上向下调用，当达到最底层后，再将函数值层层向上返回。(递下去，收回来，简称：递归)

(2)必须有个结束条件(有个该收回来的条件)

(3)可读性强

(4)计算机要记忆的数据量大，对计算机的空间占用的多，内存消耗大，不适合解决数据调用次数过多的题。

5．课堂练习

(1)下面是用递归法求1+2+3+4+…+n ，请完善程序

Public Function s(n As Integer) As Long

 If n = 1 Then

  s = ____

 Else

  s = __________

 End If

End Function

Private Sub Command1_Click()

Dim n As Integer

 n = InputBox("请输入n", "求1+2+3+4+…+n")

 Print "1+2+3+4+…+" & n & "="; s(n)

End Sub

(2)斐波那契数列0、1、1、2、3、5、8、13、21、……从第三项开始，每一项都是紧挨着的前两项的和。

Public Function s(n As Integer) As Long

Select Case n

 Case 1

  s = ______

 Case 2

  s = ______

 Case Else

  s = s(n - 1) + s(n - 2)

End Select

End Function

Private Sub Command1_Click()

Dim n As Integer

 n = InputBox("请输入n", "求斐波那契数列的第n项的值")

 Print "斐波那契数列的第" & n & "项的值"; ______

End Sub

6．作业

课本P70实践

七、教学反思

以游戏的方式引入，让学生初步明白“递归算法”。通过“猴子吃桃”问题，运用游戏的思维引导学生掌握“递归算法”的解题过程，再通过N！这个简单的数学问题，加深学生用“递归算法”解决此类题的方法。最后通过两道高中水平考试的题目，一是让学生巩固所学，二是让学生明白此类试题的考点。

参考文献

《信息技术课程与教学》   李艺  高等教育出版社2006.6出版