递归算法详解VIP免费

递归算法详解 C 通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C 语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。 这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值 4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在 printf 函数中使用了%d 格式码，它就会执行类似处理。 我们采用的策略是把这个值反复除以 10，并打印各个余数。例如，4267 除 10的余数是 7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在 ASCII 码中，字符‘7’的值是 55，所以我们需要在余数上加上 48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII 码是 48，所以我们用余数加上‘0’，所以有下面的关系： ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10 等于 426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第 2 次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状 w hile 循环。w hile 循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身 。 在程序中，递归函数的限制条件就是变量 quotient 为零。在每次递归调用之前，我们都把 quotient 除以 10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。 /*...