从计算思维的角度对递推算法与递归算法初步探讨

北京石景山社区学院 赵立群

本文主要从计算思维的角度，探讨递归算法与递推算法的模式特征和算法特点，分析了递归算法与递推算法共性和异性，以及如何用模式特征引发算法思维。在算法部分探讨了算法的要素、算法的表述关键以及算法的评价，最后对应用算法的难点进行了说明。

1 计算思维

思维是人脑对客观世界一种概括性、间接性的反映，是一种心理活动。思维具有三要素思维原料、思维主体、思维工具。思维原料就是被感知的具体事物，由自然界提供；思维主体是人脑及存在于其中的意识；思维工具是逻辑，即关于思维形式和思维规律的学说，常见的有形式逻辑、辩证逻辑等。计算思维是近些年随着计算机普及与应用，以它为工具来处理来现实问题的思维工具。维基百科中的解释为一种新的计算机科学与技术广泛使用的问题求解方法，可利用算法高效的求解大规模复杂问题。在现代科学研究中计算思维被认为是三大重要的思维工具之一，这三大工具分别为理论思维、验证思维、计算思维。其中理论思维以数学思维为代表，验证思维以物理为代表，计算思维以计算机为代表。

（1）计算思维的核心要素中公认的几个要素如图1所示，它们是抽象、分解、模式识别和算法。

图1 计算思维要素Fig.1 Elements of computational thinking

1）抽象是人们形成普遍认识规律和思想方法的基础，是指从具体事物中抽出或概括共同的性质与属性等，将非本质共性和属性丢弃的思维过程。如面向对象技术中的类和对象，C语言中处理不同问题可以使用相同的输入、输出语句等。2）分解是指将大的问题拆成小的问题的思维过程。小问题性质可以与大问题的性质一致，也可能是大问题的一部分。软件工程将软件的生态周期分为分析阶段、设计阶段、编码阶段、测试与维护阶段等，将一个大的程序分为几个功能模块等。3）模式是指一致的、有特点的形式、结构、方法或风格。模式识别是通过抽象与分解思维过程，对事物本质特征辨识和对事物依据相似性原则的分类认定。它是计算思维的核心任务，是解决问题必要步骤，掌握计算思维必须具备强大模式识别能力并在此基础上激发算法思维。4）算法是对给定的问题用可理解的形式语言表示的、对能解决此问题的一种过程的精确描述的操作序列。算法具有限性、确定性、输入、输出和有效性等五个特征。在大学计算机专业的课程中，算法应是独立于特定编程语言的，但算法与编程语言密不可分，在程序设计领域一直有“程序=数据结构+算法”的说法，可见算法对编程的意义。

（2）计算思维本质来源之一是数学思维。如现代人工智能的许多算法是数学提供的。但也有一些是来自于工程思维，如系统化方法、分治法、面向过程和面向对象方法。

2 递推与递归模式的识别

计算思维一般意义是指以计算机为工具解决问题的思维方式，它的核心手段就是通过问题的模式识别，激发处理问题的算法来解决问题。模式识别是在将对象分解成小部分（分解），将对象升华为核心特征（抽象）之时进行的。因此模式识别很好的将分解和抽象过程结合在一起。人们在算法设计的实践中，对问题的处理策略进行了总结，形成了大量的处理各领域问题以算法为标志的模式，递推和递归就是其中之一。递归与递推的共性都是将问题的处理过程分解为一个个子过程，每个问题都解决了，全部问题就解决了。不同点是递归模式是从自顶向下，从大到小的思维，它将问题分析成一个个性质相等的子问题，认为只要这个子问题处理好了，其他子问题照此方法处理即可，突出特点为处理方法一致。而递推模式从小到大，从简单到复杂的思维，它的处理不是面向全部数据的，每次只处理一部分且步步为营，逐步接近最终结果[1]。如下几个例子，说明了使用递推或递归模式解决问题的思路。

（1）有这样一个问题：你和对手做游戏，你们中的一个人可以从1或2中挑一个数字，另一个人则在对方的基础上加1或2，谁先加到20，谁就赢了。这个问题的解决从小到大思考有些难度，但如果从大到小就好解决了。如果要得到20，根据规则必须得到17，依次推理必须得到14、11、8、5、2，也就是说开始时必须抢到2你就能赢了。

（2）汉挪塔问题：有三根柱A、B、C，在柱A上有n块盘片，所有盘片都是大片的在下面，小片放在大片上面，如图2所示。现要将A上的n块片移到C柱上，每次只能移动一片，而且在同一根柱子上必须保持上面的盘片比下面的盘片小，请给出移动方法。此问题核心为首先将A上面n-1块盘片看成一个整体，把它通过C移动到B。再将第n块盘片从A移动到C。最后将B上面的n-1块盘片，通过A移动到C。然后对看做整体的n-1块盘片重复上面操作。

图2 汉挪塔图Fig.2 Hannota

3 递推和递归算法

为了研究递推和递归算法我们需要从算法的要素、算法的描述、算法的评估几个角度进行说明[2，3]。

3.1 算法要素

作为描述算法的工具，一般应考虑如下构成部分。简单的数据表示与数据存储工具、数据操作工具、流程控制工具、算法与程序设计语言。

（1）数据表示与存储工具。这部分内容应包括常见的数据形式和数据结构，如常量、变量、数组、线性表、栈、队列、树、图等。（2）数据操作工具。基本运算部分应包括以下四部分：算术运算（加、减、乘、除），逻辑运算（与、或、非），关系运算（大于、大于等于、小于、小于等于、等于、不等于），数据传送工具（赋值、输入和输出）。一个功能完整的复杂操作可以作为一个整体来使用，称为函数或过程。这个整体的数据输入可以作为函数的参数，结果作为整体的返回值。（3）流程控制工具。结构化程序设计证明流程控制只需要三种结构：顺序结构、选择结构、循环结构。所以算法的流程控制只用这三种就可表达算法在执行过程中的控制要求。（4）算法与程序设计语言。为了在计算机上执行算法，需要用计算机理解的程序设计语言，将算法翻译成程序。这个过程中要用到程序设计语言的数据表示与存储机制、数据运算机制、流程控制机制等。它们在结构化程序设计语言和面向对象程序设计语言中都有相应表示机制对应。如变量、常量、数组、结构、对象属性、各种基本运算、函数、过程、方法，类、对象等。这里要特别强调程序设计的要点是数据结构和算法，也就是说设计程序不仅要关注算法设计，还要关注解决事物的数据结构设计。

3.2 递推和递归算法描述

（1）递推的表述要点。问题的解决依赖于信息间本身的递推关系，采取步步为营的方法，不断地利用已知数据推出新的结果信息。在具体设计上要注意两点：1）问题以初值为基础，用相同的计算规律，重复计算，直到结束；2）从起点开始一直到终点的重复计算过程，用循环结构实现。

递推算法把复杂的计算转换成简单过程的重复或循环，充分发挥了计算机的速度和存储优势。如1+2+3……+n，它是真实的加了n次得到结果，而不是用数学思维的计算，即等差数列求和公式求和。这个问题的算法表述如图3所示：

图3 前n个自然数求和Fig.3 Sum of the first n natural numbers

（2）递归算法的表述要点。递归算法是把问题转化为规模缩小了的同类问题的子问题来设计算法。代码上是通过函数递归调用某些参数变小函数自身来表示问题的解。递归算法只需少量代码就可描述出解题过程所需要的多次重复计算。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。递归算法所体现的重复，一般用三点实现：1）函数在每次重复调用时应在规模上有所缩小；2）相邻两次重复之间有紧密联系，前一次的输出要为后一次的输入；3）在问题的规模缩到极小时必须直接给出解答而不再进行递归调用。

如求n!的值。它的算法伪代码如下：

此算法的执行过程如图4所示，在执行过程中它需要运行环境提供的堆栈支持以缓存中间结果，因此由于存储空间的限制，递归的深度是有限制的。

图4 递归算法的递进与返回Fig.4 Progressive and return of recursive algorithm

（3）递推与递归实现循环的差异。递推算法与递归算法都有相对简单操作的重复，递推的重复是通过相同的计算规律重复计算；递归的重复是通过缩小的同类问题的不断调用来实现。从代码角度看，一个通过流程控制的循环结构表达；另一个通过没有明显循环标志的函数与子函数的调用与返回，以程序运行环境提供的堆栈为媒介进行。那么是不是所有的递推算法都用流程控制的循环结构实现，所有的递推算法都用函数调用的递归算法实现？答案是否定的。有些情况下用递归代码可以实现递推思想，或者反过来用递推代码来实现递归思想，如表1所示。

表1 算法与代码要素的关系Tab.1 Relationship between algorithm and code elements

3.3 递推与递归算法的评估

算法的评估一般从时间复杂度和空间复杂度两个角度衡量。复杂度是指执行算法所需要的计算工作量，在计算机科学中，算法时间复杂度是一个函数f(n)，定量描述了该算法的运行时间。在计算机科学中，算法的空间复杂度也是一个函数s(n)，它定量描述算法运行时要消耗的内存空间。

（1）算法的执行时间与基本操作重复执行的次数成正比，比较容易的计算方法是看有几重循环。只有一重循环时间复杂度为O(n)，二重循环为O(n2)，以此类推。如果有二分法查找法则为O(logn)。如果一个循环套一个二分查找法，则时间复杂度为O(nlogn)。递归算法时间复杂度分析，主要根据递归过程建立递推关系式，求解这个递推关系，解到一个表示算法执行时间的表达式，最后用这个表达式表示算法的时间复杂度。

如求汉挪塔问题的时间复杂度，它的实现代码如下：

它的时间复杂度分析如下：设调用Hanoi(n，x，y，z)的执行时间为T(n)，由其执行过程得到以下求执行时间的递归关系（递推关系式）T(n)=2T(n-1)+1

（2）一个算法占用的存储空间由三部分组成：代码本身占用的空间、算法输入输出占用的空间、算法运行时占用的临时空间。算法空间复杂度分析只考虑在运行过程中为局部变量分配的存储空间，它包括两部分：参数表中形参变量分配的存储空间和在函数体中定义的局部变量分配的存储空间。若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配临时空间的大小乘以被调用次数，即递归调用的次数加1。这个1表示开始进行的一次非递归调用。

求如下递归算法maxelem(a，0，n-1)的空间复杂度。

设调用maxelem(a，0，n-1)的空间为S(n)，有：S(n)= 2S(n/2)+O(1)

则：S(n)=2S(n/2)+1=2[2S(n/22)+1]+1=22S(n/22)+1+ 21=2kS(n/2k)+1+21+22+…+2k-1（设n=2k，即k=log2n）= n×1+2k-1=2n-1=O(n)

4 结语

递归与递推算法是我们解决问题的常用工具，但其处理问题的策略有很大差异。递推是从下到上的过程，即将问题分成几部分，每部分都完成了，整个事件也就完成了，步步为营。递归是从上到下的过程，用相同处理问题的手段，逐步缩小处理范围，直到问题解决。对于要处理的问题是选择递归算法还是选择递推算法，没有一个统一的标准，要根据实际问题的需要做具体的判断，通过对算法的评估来决定。另外之所以以计算思维作为出发点，是想明确表明计算机处理问题与数学处理问题的区别，对于初学者这一点十分重要。数学思维处理问题的常规思路是逐步引用已知条件，在前面推导的基础和新引进的条件下得出新的结果，直到论证出想要的结论。这反映在计算思维上就是递推的直观思想。递归算法不像递推算法那样的具有构造性，它承认一种处理问题的概括性方法存在，但不追求实现细节，注重的是此方法处理范围的逐步缩小，进而通过这种手段解决问题。在这点上有些像数学归纳法，承认现有结论成立，想办法证明在n+1下也成立。