递归法教学的技巧浅谈 教学优秀论文

摘  要: 对初学者而言，递归算法的确很难理解。主要表现在程序的执行过程难理解，还有运用递归法解题难构思。在信息学竞赛辅导中，递归算法是学生必须掌握的基本算法。笔者在教学及自己的编程实践中总结递归算法解题的思想，结合各种图表及递归调用时系统利用堆栈后进先出的特点进行保护现场、恢复现场的细节清晰地描述来介绍递归程序的递推、回归的执行路线及执行过程中参数传递，最后介绍利用递归法解题的应用。

关键词： 递归  递推  回归  堆栈

1 引言

在信息学竞赛辅导中，学生初次接触递归算法总是觉得难以理解和掌握。虽然使用递归算法编写的程序通常都是比较简短精炼，但是他们对算法的理解总是觉得比较困难，梵尔塔那三个盘子调来调去已令绝大多数学生一头烟了。递归法难学究其原因有二：

1、对递归程序的执行过程难理解；

2、运用递归法解题难构思。

下面是笔者在实践中的一点体会，盼能得到广大教师的指导。

2        递归法介绍

其实只要弄清楚递归的思想，包括递归的定义，递归的执行过程，再灵活运用它来编程就相对容易了，而且往往几条短短的递归调用的语句就能解决用其他方法难解决的问题，其收效的确是非常奇妙的。

1、何为递归调用？

在调用一个函数模块（或过程模块）的过程中又出现直接或间接地调用该函数模块（或过程模块）本身，称为函数（或过程）的递归调用。

2、递归法包括“递推”和“回归”这两部分

2．1“递推”：

①      将原问题转化成新问题

②      新问题的解法与原问题一样，但求解过程比原问题简单些

③      不断将问题转化成更简单的新问题，直到最后的新问题有明确的答案

④      有明确终止递归条件。

2．2“回归”：指当简单问题得到解后，回归到原问题的解上来。

  下面我们通过一个例子来具体说明递归的执行过程中递归调用时系统利用堆栈后进先出的特点进行保护现场，回归时是如何恢复现场的。

3  举例

[例一]：有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁问第4个人岁数，他说比第3个人大2岁，问第3个，又说比第2个大2岁，问第2个，说比第1个大2岁。最后问第1个，他说10岁。请问第5个人多大？

显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2。即：

        原问题    新问题

age(5)   =age(4)   +2

age(4)   =age(3)   +2

age(3)   =age(2)   +2

age(2)   =age(1)   +2

age(1)   =10     （有明确的答案）

可以用式子表达如下 ：

age(1)=10         

age(n)= age(n-1)+2   (n>1)

具体求解过程可用下图表示：

从下图可知，求解可分成两个阶段：

第一阶段是“递推”，即将第n个人的年龄表示为第（n-1）个人的年龄的函数，而第（n-1）个人的仍然不知，还要“递推”到第（n-2）个人的年龄……，直到第1 个人的年龄。此时age(1)已知，不必再向前推了。

第二阶段是“回归”，从第1个人的已知年龄推算到第2个人年龄（12岁），从第2个人年龄推算出第3个人的年龄（14岁）……，一直推算出第5个人的年龄（18岁）为止。………………………………【全文请点击下载word压缩文档】
点击下载此文件