关于递归教学的探讨.docVIP

关于递归教学的探讨 鲁法明1，2 （1.大学，；2.，） 中图分类号TP311.11 文献标识码LU Fa-ming1, Bao Yun-xia2 1 (College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong 266510, China) 2(College of Science, Shandong University of Science a nd Technology, Qingdao, Shandong 266510, China) Abstract: Recursion is an important programming technique and also a difficult point in the teaching process. In this paper, with recursion as the center, the content is organized from four aspects such as what is recursion, why we need recursion, how to use recursion and the concerned problem when using recursion. The article not only describes the general method and step for recursive programming, but also describes how to design recursive algorithm through order-reducing, division and backtracking strategy with concrete examples. Keywords:Programming design; Recursion; Backtracking 引言 递归在程序设计基础、数据结构以及算法设计与分析等课程的教学中都占用重要地位，是一类重要的程序设计方法，但递归教学一直是个难点。学生通常会对为何用递归、如何用递归以及递归程序的执行过程存在疑惑。究其原因，一方面是各类教材通常只将递归作为一个概念进行简单介绍，对递归的执行过程以及递归程序设计的一般性步骤和方法描述过少；更重要的是缺少对递归程序设计方法系统性的概述。本文旨在解决这一问题，全文以递归为中心，从什么是递归、为何用递归、如何用递归以及使用递归需要注意的问题四个方面组织全文，从方法论的角度对递归程序设计进行系统的阐述。文中一方面介绍了递归程序设计的一般步骤和方法，还结合汉诺塔问题和N皇后问题等经典实例介绍了如何通过降阶、分治和回溯等策略设计递归算法。 1 什么是递归 简单来说，递归就是指函数或者过程在执行过程中直接或间接调用自身的现象。如表1中的函数即存在递归，称此类发生自身调用的函数为递归函数，通过设计递归函数进行问题求解的算法称为递归算法。 2 为何用递归 很多问题可以用递归的形式来描述，此时用递归进行程序设计简单、方便、易懂。如一个正整数n的阶乘可如下定义： 在上述定义中，F(n)=n*F(n-1)在数学中称为递归公式，实际就对应程序设计中的递归调用，F(1)=1称为递归边界。根据阶乘的这种定义，只需列出递归边界和递归公式，再加上必须的函数头、变量声明等语句便可得到一个递归函数，如表1所示。需要说明的是，如此轻而易举得到的递归函数可直接求出n的阶乘，下面分析递归函数的执行过程予以证实。 假设主函数代码如表2所示，欲求3！并输出。当主函数执行到x=F(3)时，函数F第一次被调用并开始执行，此时形参n=3，显然应执行语句result=3*F(2)；之后F第二次被调用并开始执行，此时形参n=2，显然应执行语句result=2*F(1)；之后F第三次被调用并开始执行，此时形参n=1,显然应执行语句result=1和return result，至此，函数F的第三次执行结束，返回至调用语句result=2*F(1)，注意返回后流程位于F的第二次执行中；继续执行可得result=2*1,接下来执行return result，至此，函数的第二次执行也结束并返回至调用语句result=3*F(2)处，注意返回后流程位于F的第一次执行中；继续执行得result=3*2*1,接下来执行语句return result，至此函数的第一次执行结束，返回至调用语句x=F(3)处，此时流程已回到主函数中；继续执行得x=3*2*1，如此3！被求出并赋予x，最后输出x的值