递归算法详细分析c模板.docx

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