1 / 9
文档名称:

递归算法详解.doc

格式:doc   页数:9页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

递归算法详解.doc

上传人:3188035052 2016/6/17 文件大小:0 KB

下载得到文件列表

递归算法详解.doc

文档介绍

文档介绍:递归算法详解 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 次调用还将调用自身,以此类推,似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是,事实上并不会出现这种情况。这个程序的递归实现了某种类型的螺旋状 while 循环。 while 循环在循环体每次执行时必须取得某种进展,逐步迫近循环终止条件。递归函数也是如此,它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时,它便不在调用自身。在程序中,递归函数的限制条件就是变量 quotient 为零。在每次递归调用之前,我们都把 quotient 除以 10 , 所以每递归调用一次, 它的值就越来越接近零。当它最终变成零时,递归便告终止。/* 接受一个整型值(无符号 0 ,把它转换为字符并打印它,前导零被删除*/ #include <> int binary_to_ascii( unsigned int value) { unsigned int quotient; quotient = value / 10; if( quotient != 0) binary_to_ascii( quotient); putchar ( value % 10 + '0' ); } 递归是如何帮助我们以正确的顺序打印这些字符呢?下面是这个函数的工作流程。 1. 将参数值除以 10 2. 如果 quotient 的值为非零, 调用 binary-to-ascii 打印 quotient 当前值的各位数字 3. 接着,打印步骤