如何学好“递归算法”

发表时间:2018/7/5   来源:《素质教育》2018年8月总第281期   作者:尤凤森
[导读] 只要采用合适的案例引入,让学生自己实践,通过讲解,可以把递归变得简单。

山东省牟平第一中学 264100  
        在《信息技术选修---算法与程序设计》中,学生普遍认为递归算法有一定的难度。对于递归的思想,其实从“从前有座山,山上有座庙”中学生已经有一点点了解,但把递归的思想运用到程序设计中,来解决一些问题,对于学生来说,还是有一定的难度的。但我想,只要采用合适的案例引入,让学生自己实践,通过讲解,可以把递归变得简单。
一、合适的案例引入,了解递归
        在广东版的递归算法中,采用的案例引入是斐波那契的兔子问题引入的。我觉得这个案例可以用于第二个案例来讲解。我讲这节课时,是用递归计算n!作为引入案例。


我是这样来分析这个问题的:
        学生通过数学知识可知:
        n!=n*(n-1)*(n-2)*……*3*2*1,
        而(n-1)*(n-2)*……*3*2*1又可以写成(n-1)!,
        所以n!又可以写成n!=1           当n=0时,
                         n!=n*(n-1)!  当n>0时。
        根据公式,可以将求n!的问题变成求(n-1)!的问题,因为当(n-1)!求出以后,再乘以n就是n!,而求(n-1)!的问题,又可以变成求(n-2)!的问题,求(n-2)!的问题又可以变成求(n-3)!的问题,如此继续,直到最后变成求0!的问题,而根据公式,0!=1,再反过来求出1!,2!,……(n-1)!,n!。
        递归的思想是直接或间接地调用自身的算法,调用自身算法的目的是把一个比较大的问题,层层转化为一个与原问题相类似、规模较小的问题,即n的问题化成(n-1)的问题,一直化到递归的出口,即1的问题,从而得到原问题的解。
二、动手实践,亲自体会递归的调用
        很多课本中,只要是涉及到递归算法,就会提出汉诺塔的问题,与前面的案例相比,汉诺塔的问题更能让学生体会到不同参数之间的变化问题,能让学生在对递归有一定了解的情况下更好地来理解递归的调用。
三、拓展延伸,深层分析算法,用递归来解决问题
        学生掌握了递归的思想、算法和调用过程后,可以给学生提供一些需要分析问题,设计算法来解决的问题。
        问题1:阿克曼函数问题(与n!相似,可以根据公式写出递归函数)
        问题2:斐波那契的兔子问题。(需要分析,得出当前月的兔子数量与前两个月兔子数量的关系,从而得出递归式)
        问题3:上楼梯时,有时一步一级楼梯,有时一步两级楼梯。如果楼梯有N级,上完这N级楼梯有多少种不同的方法?
        通过拓展延伸,让学生意识到,用递归可以解决很多复杂的问题但不需要很复杂的步骤。同时,也要向学生说明,并不是所有的问题都可以用递归来解决的。


 

投稿 打印文章 转寄朋友 留言编辑 收藏文章

  期刊推荐
1/1
转寄给朋友
朋友的昵称:
朋友的邮件地址:
您的昵称:
您的邮件地址:
邮件主题:
推荐理由:

写信给编辑
标题:
内容:
您的昵称:
您的邮件地址: