ACM基础算法之递归

递归算法详解 递归算法是ACM基础算法之一，通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。许多教科书都把计算机阶乘和菲波那契数列用来说明递归，但是这些例子并没有提供任何优越之处。 本文通过一个简单的程序，用于说明递归的实现。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。我们采用的策略是把这个值反复除以10，并打印各个余数。 在这个程序中，我们使用递归来解决问题。递归函数的工作流程可以分为三步：将参数值除以10，如果quotient的值为非零，调用binary-to-ascii打印quotient当前值的各位数字；接着，打印步骤1中的除法运算的余数。 递归函数的实现是基于函数调用自身的原理。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。然而，事实上并不会出现这种情况。这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。 在这个程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。 递归是如何帮助我们以正确的顺序打印这些字符的呢？下面是这个函数的工作流程： 1. 将参数值除以10 2. 如果quotient的值为非零，调用binary-to-ascii打印quotient当前值的各位数字 3. 接着，打印步骤1中的除法运算的余数 注意在第2个步骤中，我们需要打印的是quotient当前值的各位数字。我们所面临的问题和最初的问题完全相同，只是变量quotient的值变小了。我们用刚刚编写的函数（把整数转换为各个数字字符并打印出来）来解决这个问题。由于quotient的值越来越小，所以递归最终会终止。 一旦你理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误，你的限制条件设置正确，并且每次调用之后更接近限制条件，递归函数总是能正确的完成任务。 然而，为了理解递归的工作原理，你需要追踪递归调用的执行过程，让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上，但他们被新函数的变量所掩盖，因此是不能被访问的。 当递归函数调用自身时，情况于是如此。每进行一次新的调用，都将创建一批变量，他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时，必须把分数不同次调用的变量区分开来，以避免混淆。