从计算思维的视角辨析算法中的递归与迭代

来源:用户上传      作者:

　　算法思维是计算思维的一个方面，而在计算机科学中，基于递归和迭代的思维方式在算法和程序设计中广泛应用，是算法思维的重要构成部分。因此，信息技术学科教师在基础课教学中辨析递归与迭代算法，将其作为发展学生计算思维的一项内容，值得探索和实践。
　　递归算法与迭代算法概述
　　无论是使用计算机还是日常解决问题，人们往往会碰到这样一些情况：一个问题刚开始难以解决，但可以将其简化后再尝试解决;如果这样解决问题的过程可以重复进行，待解决的问题最终会变得容易处理。在算法和程序设计中，这样的过程引出了两种不同的方法：递归和迭代。
　　递归算法蕴含着计算机学科的一些基本思想方法，它能为某些问题提供简便的解决方案。递归算法是指一种方法被直接或间接地调用“自身”的过程。其基本思想如下：先将一个复杂的问题转化为规模缩小了的类似子问题，设计出针对此子问题的解决方法，然后再次使用这样的方式，直到缩小的问题变为直观的可以解决的问题。例如，计算机算法中的“对分查找”问题可以采用递归算法这样设计：在一个确定的已经排好序的数组中，将“查找键”和“数组中点位置元素”不断地进行对比，根据对比结果，每次缩小一半的查找范围，反复进行，最终问题变为查找范围只有一个数组元素，此时只要让查找键和这最后一个数组元素比较，查找结果就很容易得出。
　　迭代本是数学中的一个重要方法，只是随着计算机科学的快速发展，借用计算机运算速度快等特点，迭代思想逐步演化为迭代算法。其基本思想如下：让计算机对一定步骤（或一组指令）进行重复操作，在每一次执行这些步骤后，都能用变量的旧值（初值）计算出一个新值，通过新值的逐渐变化，达到（或逼近）最终结果的目的。例如，计算机算法和程序设计中的累加求和问题，通过设置一个变量（累加器），在循环结构中，每次执行都让一个“数据”累加到这个变量中，通过控制循环次数，可以达到最终所需要的结果。
　　递归算法与迭代算法在算法和程序设计中应用非常广泛，因此也可以认为是计算思维的重要内容，但对于高中学生来说，一开始往往难以理解。在教学实践中，笔者认为可以通过具体的案例入手，用案例教学法，通过对比分析来促进学生的理解。
　　一个算法实例
　　斐波那契数列（Fiboncci Sequence），又被称为黄金分割数列，是指这样一个数列：1、1、2、3、5、8、13、21……（即后一个数字是前两个数字之和）。在数学中，该数列直接被以递归的形式定义：f（1）=1，f（2）=1，f（n）=f（n-1）+f（n-2） （n>2，n∈N）。在教学实践中，笔者发现很多一线教师都会用“斐波那契数列”来作为教学实例，通过求解该数列第n项的问题设计算法。下面以求“斐波那契数列的第20项数值”為例，分别用递归和迭代算法表示。
　　1.用递归算法实现
　　递归算法是反复调用“自身”的过程，因此我们可以先定义一个函数[如f（n）]，然后在算法执行中反复调用这个函数。基于VB语言，实现过程如图1所示。
　　当然，用递归的方式解决该问题，也可以不定义函数，而采用数组变量的方式实现，程序代码如图2所示。
　　以上两种方式，其实质是一样的，都是根据该数列的数学定义，从第三项开始，对前两项求和的反复使用。
　　2.用迭代算法实现
　　虽然斐波那契数列的数学定义是采用递归的形式，但用迭代算法一样能够解决，解决方案是先定义三个变量（如f1、f2、f3），然后对变量进行更新赋值，同时利用循环控制执行过程。基于VB语言，采用迭代算法解决这个问题的程序代码如图3所示。
　　当然，针对这个问题，也可以只采用两个变量实现，只需将“图3”循环体内代码换为“f1=f1+f2：f2=f1-f2”，同时将输出的内容换为“Str（f1）”。
　　3.递归与迭代算法的简单对比
　　就“求斐波那契数列的第20项数值”问题而言，由以上分析我们可以看到，用递归算法和迭代算法都能实现，但从算法执行效率方面考虑，二者还是存在一定的差别的。
　　从“图1”解决该问题的描述来说，在程序主语句中，对于n>3，每调用一次函数f，其实都会引起两次该函数的调用。因此，如果求解的项数值比较大，调用函数f的总次数按指数增长，如此例中求第20项，函数f被调用次数近百万次，显然这样的一个程序是不太实用的。而“图3”中采用迭代算法实现该问题，就避免了同一值的重复计算问题，循环体内只是执行了54[（（20-3）+1）*3]次的赋值运算，显然效率更高。当用计算机解决一个问题时，一般存在多种不同的方法。对于较小的问题，只要管用，方法不同并没有什么关系。但对于大型问题或者需要解决大量小型问题的集合，我们就需要考虑算法的效率问题了。
　　在解决实际问题时，递归算法和迭代算法之间可以转换，但它们的计算机执行效率也并不是都和上例一样——迭代优于递归，但要具体问题具体分析。例如，另一个经典算法案例“汉诺塔问题”，其递归算法中有两处递归调用，并且其中一处的调用语句后面还有其他的非递归调用语句，要把这样的问题用迭代的方式实现，相对比较复杂，并且它们并不会明显提高程序的执行效率，反而会使程序“不易读”。
　　递归和迭代在算法和程序设计中作为特别有用的工具，可以帮助我们解决一些表面看起来非常复杂的问题。在教学实践中，通过选择合适的实例，并分析设计算法最终实现，可以帮助学生更好地理解其基本思想，培养算法思维。同时，在分析中如果对比算法执行效率的问题，其实也是算法不断优化思想的体现，这些都是发展学生计算思维的要义所在。
　　从计算思维的角度看递归和迭代
　　计算思维涉及一些必要的思维技能，包括抽象和分解、递归思维、问题减少和转换、错误预防和保护以及启发式推理等，这些都是解决复杂问题所必需的。无论是日常生活还是在程序设计中，计算思维和程序设计应该被看作独立但兼容的认知工具，它们都扩展了问题解决的方式。递归和迭代作为计算思维的构成内容，同样如此。作为算法，它们在程序设计中广泛存在。其实从算法先于并且独立于程序设计的角度，递归和迭代作为一种思维方式，普遍存在于我们解决问题之中。从计算思维的视角，在实现解决问题的过程中，它们具有以下特性。 　　1.问题分解
　　在NRC计算思维教学研讨会报告中，Tinker曾说过：“计算思维的核心是将大的问题分解成很小的问题直到小的问题能够自动化解决的思维过程。”递归和迭代可以说最好地反映了这样的思想。在递归中，我们常说是调用“自身”的过程，这里的“自身”两字往往是加了引号的，事实上，递归算法中的定义从来不是按某一事物本身来定义的，而是以比自身简单一些的说法来定义。通过反复调用简单的来实现复杂的功能，这里的简单“自身”，其实就是对问题的分解。同样，“迭”是屡次和反复，“代”就是替换，简单来说，迭代就是反复替换的意思。事实上，在进入替换之前，有一个“初始化”的过程，这个过程是根据问题本身的特点，找到简单的已知的部分（如数列的初项等），在反复替换中达到解决问题的目的。像递归和迭代这种将一个复杂问题先简单化处理的思想方式，很好地体现了计算思维的问题分解的特点。
　　2.问题构造
　　在递归算法设计中，很重要的一点就是递归的逐层深入后必须有一个结束递归的条件或边界，以逐层返回获得结果。而在迭代算法中，实现反复替换的是循环结构控制，它由以下三部分组成：①初始化：建立初始状态，这一初始状态会沿着终止条件变化;②测试：比较当前状态和终止状态，如果两者相等，就结束循环;③修改：向着终止条件的方向改变状态。也就是说，无论是递归还是迭代的使用，都是有终止的，问题简化到一定程度，一定是可以解决的，其实这体现了解决问题的构造性特点，这也是计算思维的特征之一。
　　3.形式化表达
　　周以真认为：计算思维的本质是抽象和自动化。也可以这样说，计算思维中的抽象是为了实现自动化而做的两种抽象：一是过程抽象，即将解决问题的过程用形式化表达;二是对象抽象，即用数据（变量）来表示对象。实现迭代算法的循环控制和实现递归算法的函数（过程）调用，都是简洁而漂亮的形式化方式，它们在程序设计中已经存在标准的模型，可以方便地将复杂问题的解决过程进行形式化描述。形式化表达，既是计算机程序设计中对算法的要求，其实也是人们在解决实际问题过程中思维可视化的要求，所以也是计算思维的重要特征。
　　计算思维反映了计算机学科的核心方法和本质，递归和迭代算法很好地反映了计算思维的特征。因此，在信息技术学科教学中，应该对学生进行递归和迭代算法的训练，从而促进学生计算思维的发展。
　　结语
　　很多研究者提出，计算思维的教育不能仅仅停留在利用计算机解决问题上，而应该通过问题解决方法的实践来理解人与计算机的关系。但我们也應该看到，计算思维是建立在计算机科学和计算机应用层面之上的概念，如果脱离信息技术课程的具体内容，单纯讨论计算思维的培养是很困难的。因此，我们应该根据不同学段学生的心智特征，针对性地梳理反映计算思维核心特征的教育内容，将计算思维的培养整合到这些内容的具体教学活动之中。
转载注明来源:https://www.xzbu.com/9/view-15235439.htm