程序设计中递归函数教学问题探究

摘要:递归问题是程序设计语言教学中的一个重点、难点内容,针对递归教学的教学特点,阐述递归函数的精髓和教学方法,提出将理论和实践结合起来,通过剖析学生在学习递归函数时产生的错误和误区,应用实例和类比策略帮助学生解决递归函数学习中存在的问题,取得了事半功倍的教学效果。

关键词:递归函数;递归教学;程序设计基础

递归是计算技术中的重要概念之一,与递归有关的概念有递归关系、递归数列、递归过程、递归算法、递归程序、递归方法。递归不仅应用于算法与程序设计之中,还广泛地应用于定义序列、函数和集合等各个方面。对递归的理解和应用,有助于提高学生的计算思维。

尽管递归的概念很重要,但部分学生对递归的理解和应用还较为困难,尤其对刚接触程序设计的初学者来说,什么场合下使用递归的方法,使用递归的方法应注意哪些问题等还存在不少困惑。本文针对递归函数教学中的一些教学方法进行了探讨,对学生容易产生问题的知识点进行了着重阐述,让学生牢固掌握递归程序设计方法,将所学知识融会贯通以解决实际问题。

1递归函数

递归函数指的是函数直接或间接地调用“自身”。从图1中可以看到,这两种递归调用都是无终止的自身调用,显然在程序中不应出现这种无终止的调用,而只应出现有限次数、有终止的调用。在以上的关于递归函数的定义中,调用自身中的“自身”两个字加上了引号。若不加引号,就会出现循环定义的问题。事实上,递归是以比自身简单一些的说法来定义的,即在计算结构相同的情况下,使计算的规模小于自身[1]137。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

2递归的精髓与设计难点

递归算法在可计算性理论中占有重要地位,它是算法设计的有力工具,对于拓展编程思路非常有用[2]。就递归算法而言并不涉及高深数学知识,只不过初学者要建立起递归概念不十分容易。因此,在教学中所采用的教学线路是先用一个简单的例子导入递归的概念,归纳出递归的要素;接下来采用实例教学的形式,给出递归执行的过程,让学生对递归建立感性认识;接下来给出递归问题的求解过程,一般分为数值型递归问题和非数值型递归问题,由于学生对数值型递归问题的理解要好一些,所以首先给出数值型递归问题求解再介绍非数值型递归问题求解。

2.1递归函数的执行过程

在教学中首先从一个简单的递归程序开始分析递归程序求n的阶乘的执行过程,通过对递归程序的执行的分析,可以打消初学者对递归程序功能的怀疑心理。n的阶乘是这样定义的:

0!= 1

n!= n • (n-1)!(n>1)

图2以求3!为例,分析递归函数fact(n)的执行过程,求n!程序见2.2节。3!=3*2!,2!=2*1!,1!=1*0!=1*1=1,知道了1!=1再反过来算回去,2!=2*1!=2*1=2,3!=3*2!=3*2=6。

int main()

{int p;

p=fact(3);

printf(“%d”p);

}

1)main()函数有一个局部变量p,如图2所示。

图2递归函数fact的执行过程

2) 每次调用函数时为参数和局部变量分配存储空间,退出函数时释放它们的存储空间。调用fact (3)时要分配参数和局部变量的存储空间,其中n已初始化为3。

3)fact (3)又调用fact (2),又要fact (2)的参数和局部变量分配存储空间,其中n已初始化为2。fact (3)和fact (2)是两次不同的调用,fact (3)的参数n和fact (2)的参数n各有各的存储单元,虽然在写代码时只写了一次参数n,但运行时却是两个不同的参数n。并且由于调用fact (2)时fact (3)还没退出,所以两个函数调用的参数n同时存在。

4) 以此类推,可以得到整个调用过程。这个过程和前面我们用数学公式计算3!的过程是一样的,都是先一步步展开然后再一步步收回。

在计算机系统中,执行递归函数是通过栈来实现的。当主函数main()调用阶乘函数fact()时,系统就自动为递归建立一个工作栈,栈中每个结点就是一次递归调用的数据区。函数被调用时,则栈内增加一个与其对应的结点,当函数调用完毕后(注意包括它调用的子函数),与其对应的结点出栈。增加一层递归,栈内就要增加一个结点;反之,当结束一层递归调用,栈内就要删除一个结点。

递归函数的执行过程依然是普通的函数调用过程,所谓递归函数调用自身,实质上是一系列的函数顺序执行的结果,只不过这些函数有相同的代码段,但是有不同的数据段。所谓递归的层次就是函数调用的深度。由于递归函数有相同的处理过程,因此用于表示递归调用的栈的结点是相同的结构类型,而一般的函数调用有不同的形参表。

2.2数值型递归问题的求解

数值型递归问题一般都有明确的递推公式和初始条件,对于这类递归问题编写递归程序的一般方法是:建立递归数学模型,确立递归终止条件,将递归数学模型转换为递归程序[3]。从数学公式入手,推出问题的递归定义,然后确定问题的边界条件,这样就可以确定递归的算法和递归结束条件。下面的例子为用递归算法求n!。

定义函数fact(n)=n!,fact(n-1)=(n-1)!,则有fact(n)=n*fact(n-1),边界条件为fact(1)=1,fact(0)=1。

程序如下:

longfact(int n) /*函数定义*/

{long result;

if (n==1 || n == 0) /*递归出口*/

result = 1;

else

result = n * fact(n-1);/*递归步骤 */

return result;

}

2.3非数值型递归问题的求解

由于非数值型递归问题本身难于用数学公式表示,对于此类问题采用的是分治法,将一个大问题分解为两个或更多小问题,使原来的大问题变成小问题的组合,问题的规模比原来的规模要小,这是非数值型问题求解的最关键的步骤。编写非数值型递归问题的一般方法是:确定问题的最小规模,分解原来的非数值型问题建立递归模型,确定递归的终止条件,将递归模型转换为递归程序。下面以汉诺塔问题为例具体说明非数值型递归问题的求解过程[4]。汉诺塔问题经过抽象之后,设总任务为Move(n, A, B, C)表示将A杆上的n个盘子借助于C杆移动到B杆上去,则需要以下三个子任务来完成,子任务是用任务自身来定义的,但规模要小于任务自身。

1)Move(n-1, A, B, C),将上面的n-1只盘子作为一个整体从A经B移至C;

2) 输出n:A to B,将n号盘从A移至B,是直接可求解结点;

3)Move(n-1, C, B, A),将上面的n-1只盘子作为一个整体从C经A移至B。

该递归程序的算法如下。

hanio(n个盘,A→B)// C为过渡

{ if (n == 1) 直接把盘子A→B

else{

hanio(n-1个盘, A→C)

把n号盘 A→B

hanio(n-1个盘, C→B)

}

}

3递归教学分析及解决方法

在递归教学过程中,对学生的程序进行分析发现学生存在一些共性的错误和误区。对于学生存在错误和误区,在教学中让学生反复练习教师着重强调的方法,提高学生对递归问题的感性认识,加深对递归思想的理解,逐步完善递归函数的学习,以期取得较好的教学效果。通过对几年来的学生上课及考试数据观察,学生从初次接触递归到初次课堂练习到初次作业情况到再次接触递归函数程序设计到最后考试,学生犯错误的比例依次在降低,对递归函数的理解和编程水平不断提升。以下是笔者总结学生在学习递归时需要有真对性强调的几点。

3.1递归结束条件的正确应用

int fact(int n)

{

returnn * fact(n - 1);

}

通过运行这个不正确的递归函数向学生阐明递归结束条件的重要意义。没有递归结束条件,它会永远运行下去,直到程序缺少内存或者栈空间,因为它没有终止的地方。函数会连续不断地调用fact()。 当计算到零时,没有停止条件,所以它会继续调用零和负数的阶乘。

3.2递归函数调用中的变量和参数的正确理解

在函数的递归调用过程中,并不是重新复制该函数,而是重新使用新的变量和参数。函数中的局部变量和参数只是局限于当前调用层,当递推进入“简单问题”层时,原来层次的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。例,求1+2+…+100的和。

递归变量的确定问题,从题目上看应该取1,2,…,100这些变量的值作为递归的条件;如何确定终止条件,从题目上看应该是当数为100的时候就不能往下加了。那么给出以下程序。

int sum(int num)

{

int count=0;

count=count+num;

if (num==100) return count;

sum (++num);

}

这里有一个问题一定要注意,就是int count。如果使用int count=0这样的语句,在每次调用函数sum()的时候,count的值都是赋值为0,也就是第一步虽然加了1上来,可是第二次调用的时候,count的值又被重新赋值为0。每次递归调用都使用新的参数和变量,因此最后结果一定不是期待的5050而是100。static能保证本次初始化的值是上次执行后的值,这样也就保证了前面想加的结果不会丢失,所以正确的程序将int count=0;修改为static int count=0,才能得到正确的结果。

3.3递归与循环

递归和循环是两种软件思维,两者之间既有区别又有很多类似之处。递归与循环都是在一定程度上重复执行某一程序段,区别在于使用递归函数极少被迫修改任何一个变量,只需要将新值作为参数传递给下一次函数调用。这就使得可以获得避免使用可更新变量的所有益处,同时能够进行重复的、有状态的行为。使用递归编程代码简洁,程序的正确性容易验证;采用循环设计可以节省程序执行时的内存消耗,两者可以相互转换,有时只能用递归思想解决。

3.4递归与迭代

“迭代”就是反复替换的意思[1]139。在程序设计中,为了处理重复性计算问题,最常用的方法就是迭代方法,主要是循环迭代。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。迭代与递归有着密切的关系,甚至,一类如X0=a,Xn+1=f(n)的递归关系也可以看作是数列的一个迭代关系。可以证明,迭代程序都可以转换为与它等价的递归程序,反之,则不然。就效率而言,递归程序的实现要比迭代程序的实现耗费更多的时间和空间。因此,在具体实现的时候又希望尽可能将递归程序转化为等价的迭代程序。下面给出求解第n项斐波那契数列的递归法和迭代法。

递归法的部分关键代码如下。

if (n == 1|| n== 2)return 1;

elsereturn fib (n - 1) + fib(n - 2);

迭代法部分关键代码如下。

假设开始时f0=1,f1=1, Fib表示当前斐波那契数,则:

For (i = 1; i < n; i++)

{

Fib = f0 + f1;

f0 = f1;

f1 =Fib;

}

这样迭代结束时Fib就是fib(n)了。

4结语

递归是一种常用的程序设计技术,采用递归编写程序能使程序变得简洁和清晰。本文从教学实践出发,分析了学生在学习递归函数时普遍存在的困惑问题,采用了有真对性的授课方式,突出重点,强化难点,加深学生对递归思想的理解,提高学生对递归函数的应用能力。

参考文献:

[1] 董荣胜. 计算机科学导论:思想与方法[M]. 北京:高等教育出版社,2007.

[2] 董荣胜,古天龙. 计算机科学与技术方法论[M]. 北京:人民邮电出版社,2002:106.

[3] Roberts,E.S. 程序设计抽象思想:C语言描述[M]. 闪四清,译.北京:清华大学出版社,2005:152-156.

[4] 李凤霞. C语言程序设计教程[M]. 2版. 北京:北京理工大学出版社,2008:210-212.

Discussion of Teaching on Recursive Fuction in Program Design Course

WANG Hui-jiao

(School of Computer & Control, Guilin University of Electronic Technology, Guilin 541004, China)

Abstract: Recursion is an emphases and a difficult matter in the teaching of program design. Aim at the characteristic of the teaching of recursion, the kernel of recursive fuction and teaching means of the recursion are expounded. The usual mistake of the students’ occurring in the recursion is parsed by theory combined with practice. It can help students solve the exist problems when they study the recursion by using examples and the strategy of analogy, and it get twice the result with half the effort.

Key words: recursive function; teaching of recursion; program design basis

(编辑:白杰)

推荐访问:递归 探究 程序设计 函数 教学