循环、迭代与递归

方悦

摘要：该文对比了循环、迭代与递归在概念、用法和性质上的异同，以阶乘和Fibonacci数列为例在c语言和汇编语言环境中进行说明。

关键词：循环;迭代;递归;阶乘;斐波那契数列

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2020）06-0055-03

任何复杂的事物都是由简单的东西发展演变而来的，让我们来从头说起。这里最初始的概念是重复/反复（repeat），意思是一遍又一遍（again and again），是相对于“只做一遍”而言的。从强调“行为次数”到以“执行路径”为关注点，我们引入了循环。循环（100p）的概念源自对环（cycle）这种物理形状的逻辑抽象，用于形容运行过程的周而复始。在计算机程序设计中，“循环”这一术语指的是一种专门的控制结构。特征是重复执行循环体中的语句，比一般情况下的顺序执行复杂一些，需要跳转命令和条件判断组合实现。循环侧重于解决问题的过程，至于方法，主要有迭代和递归两种。根据《简明数学词典》的定义，迭代（Iteration）指的是重复执行一系列的运算步骤，直到求得最终结果，特点是每一次迭代得到的结果都作为下一次迭代的初始值。在计算机领域，上述“一系列的运算步骤”如果用“子程序”这个词来代替就容易理解了。在此，迭代是用重复更替的方法，实现了更新变量数值的目的。有别于直接法（或者称为一次解法），即一次性解决问题。讲完了迭代，再来看递归。不过在谈递归之前，引入另外一个词：递推。递推与递归，一字之差，却有不同，我们先看区别。从字面来简单理解，递推就是“以此类推”的意思。根据《中国中学教学百科全书·数学卷》定义，递推是将复杂运算化简为若干步重复的简单运算。听起来有一些抽象。其实递推本是一个数学概念，源于数列。我们知道，如果数列{an}的第n项依靠其前一项或几项确定，这种关系就叫递推。例如：经典的等差数列an=an-1+d、等比数列an=aa-1q、斐波那契数列（Fibonacci Sequence）an=an-1+an-2（n>=3，a1=1，a2=1），等。在计算机科学中，这种由初值求终值的递推式理所当然用迭代法来实现。

那么什么是递归呢？维基百科（Wikipedia）给出了这样的诠释：Recursion is the process of repeating items in a self-similarway.意思是说递归f或递推）就是用自相似的方法进行重复。何为“自相似”？根据《数学辞海·第五卷》定义，当该集的任一个局部放大适当倍数后，它的形状将会和其原来的整体相一致。如何做到这一点呢？在数学与计算机科学中，递归通过在函数（子程序）的定义中使用函数（子程序）自身这种方法实现。后面的例子中我们将会看到，递归的求解包含“遞推”和“回归”两个过程。有趣的是，我们发现递推和递归的英文都是Recursion，二者是不做区分的，都是指用相同的方法进行自我更替。举个大家熟悉的例子：从前有座山，山里有座庙，庙里有个和尚讲故事，讲的什么呢？从前有座山，山里有座庙，庙里有个和尚讲故事，讲的什么呢？从前有座山，山里有座庙，庙里有个和尚讲故事，讲的什么呢？……根据定义，这是典型的递归，同时也是一种递推，在此过程中用到了迭代。在中文的语境，递推暗含方向朝前（forward），而递归描述的是方向往回（back）。递归和递推的共同点在于“递”，强调使用相同算法更新迭代，所以二者在英文中是用分形来定义的。事实上，从严格的意义上讲，递归除了有一般的自递归，还包括互递归。互递归，是通过调用其他函数间接地调用自身的过程。此外，在C语言中，还有一个嵌套函数的概念。所谓嵌套函数，指的是在某些情况下，可能需要将某函数作为另一函数的参数使用，这一函数就是嵌套函数。在一个函数被调用的过程中又调用另一个函数，这就是函数的嵌套调用。特别的，如果是函数本身嵌套调用函数本身，那就是函数递归调用了。递归调用是嵌套调用的特殊情形，递归调用的本质就是对同一个子程序（函数）的嵌套调用。接下来我们以c语言和汇编语言条件下求阶乘n！为例。

可以很清楚地看到，C语言中的循环在汇编环境下是用简单的：比较指令cmp+跳转指令（如jmp）的组合来实现的，这与我们下面谈到的递归方法有所不同。

这里略微复杂一些，C语言中的递归调用factorial（n-1）是用call指令完成的。我们知道，call调用一个子程序的步骤是push+jump，即在堆栈中先用eax保存参数n-1，再跳转到函数入口f013813C0）循环调用.factorial。此过程与迭代的相同之处是都含有计数器和参数的变化、并且都有出口条件保iiEN环次数有限，不同的地方是：迭代过程更新的是所求未知量，循环结束就能求得目标结果;递归过程由两部分组成，其分界线是到达函数出口（01381403）。前半部分压栈操作（call）完成的只是参数的准备工作（1、2、3、……、n），后半部分弹栈操作（retn）完成的才是实际计算（resuh=lx2x3x……×n）。从形式上可以看出，迭代一般只是“0型”的循环结构，而递归则是“8型”的循环结构，换句话说是由两个循环连接组成的，见图1：子程序的调用过程。

我们发现，递归主要分为两步，第一步是从目标出发回溯到源头，称为回归。第二步是从源头出发逐步回代达到目标，称为递推。这就必须保存子程序的变量、参数与返回地址，使程序能够返回到调用处继续执行。这一步是通过栈来实现的，做法是将函数的返回地址（也称为“断点”）即该函数下一条待执行指令的地址压栈。反复call（调用）子程序相当于是“回归”过程，多次执行ret（返回）指令就相当于“递堆”过程。每一个call都会有一个ret与之对应，并且是某一级递归返回到调用它的那一级，而不是直接返回到main（）函数中的初始调用部分。虽然每一级递归都有自己的变量和参数，但是函数代码并不会复制，变化的主要是栈区的数据，下面我们用图示来进一步观察和分析。

递归算法实质就是一个函数不断调用自身的过程，在调用过程中不断地将局部变量、函数参数和返回地址压人栈区，当返回时再将栈恢复到每一次调用前的状态，每一层调用过程栈帧中存放的返回地址都是相同的（013813F9）。在整个的返回阶段，始终以EAX寄存器作为桥梁，反复和栈交换数据，不断地将中间結果保存在返回值中，从而实现参数的传递和结果的返回。

由此可见，递归确实是一种奇妙的思维方式。其优点是很显然的：容易理解，容易编程。不过，PeterDeutsch（彼得·道奇）曾说：To Iterate is Human，to Recurse，Divine.（用迭代的是人，用递归的，是神。）他想表达的意思是：递归虽好，能够用对却不容易。当我们面对一个复杂问题的时候，应当想想能否将其转化为较为简单的同类问题呢？可以的话，就先转换为简单的同类问题来解决，然后再利用简单的同类问题解法来解决复杂的同类问题，这就是递归思维方式的精髓所在。

递归的使用是有条件的。只有当算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。从数学角度讲，有这几种表达方式：函数具备收敛性=有确定的（或有限的）极限=极限是（确定的点或有限的数），对于计算机来说也一样，要求约束条件必须收敛。简而言之，循环次数是有限的，即有一个明确的边界条件或临界点，作为递归出口。为做到这一点，递归函数中必须包含终止递归的语句。通常递归函数会使用一个if条件语句或其他类似语句以便当函数参数达到某个特定值（如上例的n=1）时结束递归调用。

递归和循环是两种不同的解决问题的思路。单从算法设计上讲，递归和循环并无优劣之分。然而，在编程开发中，由于函数调用的开销，递归常常会带来性能问题，特别是在求解规模不确定的情况下;而循环因为没有函数调用开销，所以效率会比递归高。我们以计算Fibonacci（斐波那契）函数为例来说明。

对于应用程序而言，时间开销和空间开销是两个重要的考察项目。从时间的角度来看，递归存在计算速度慢、执行时间长的弊端，时间复杂度0（2ⁿ）呈现指数级的增长，相比于循环的线性变化0（n）要高得多，原因在于不必要的重复计算。下图是n=5时的递归树（recursion tree），可以看出虚线框中Fibonacci（2）的计算用到了三次，同样的Fibonacci（3）的计算用到了两次，显然我们进行了不少的重复运算。不得不考虑到，当n越大时，情况越严重。

从空间的角度来看，循环使用的是堆空间，而递归使用的是栈空间。循环占用的内存是一次性的，也就是O（1）的空间复杂度，而对于递归（不考虑尾递归优化的情况），每次函数调用都要压栈，那么空间复杂度是O（n），和递归次数呈线性关系。

综上所述，循环、迭代与递归、递推这几个概念既有联系，又有区别。它们是人们解决复杂问题的思想方法，无论是在阅读还是在表达时，不管是在学习还是在工作中，都应做到准确理解和正确使用。