C语言中递归算法函数的实现代码

  次阅读 作者:智能小宝 来源:互联网 2016-01-26 10:16 我要评论(0)

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 <stdio.h>

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. 接着,打印步骤1中除法运算的余数

注意在第2个步骤中,我们需要打印的是quotient当前值的各位数字。我们所面临的问题和最初的问题完全相同,只是变量quotient的 值变小了。我们用刚刚编写的函数(把整数转换为各个数字字符并打印出来)来解决这个问题。由于quotient的值越来越小,所以递归最终会终止。

一旦你理解了递归,阅读递归函数最容易的方法不是纠缠于它的执行过程,而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误,你的限制条件设置正确,并且每次调用之后更接近限制条件,递归函数总是能正确的完成任务。

但是,为了理解递归的工作原理,你需要追踪递归调用的执行过程,所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声 明的变量是如何存储的。当函数被调用时,它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上,但他们被新函数的变量所掩盖,因此 是不能被访问的。

当递归函数调用自身时,情况于是如此。每进行一次新的调用,都将创建一批变量,他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时,必须把分数不同次调用的变量区分开来,以避免混淆。

程序中的函数有两个变量:参数value和局部变量quotient。下面的一些图显示了堆栈的状态,当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影,表示他们不能被当前正在执行的函数访问。

本站文章信息来源于网络以及网友投稿,本站只负责对文章进行整理、排版、编辑,是出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如果您有什么意见或建议,请联系QQ28-1688-302!

人工智能实验室
相关文章相关文章
  • 韩春雨称已能重复实验结果 近期将有消息公布

    韩春雨称已能重复实验结果 近期将有消息公布

  • 未来两年人工智能要怎么走?看这篇就够了

    未来两年人工智能要怎么走?看这篇就够了

  • 英国研发“杀生”机器人 通过生命体获取能量

    英国研发“杀生”机器人 通过生命体获取能量

  • 无人驾驶汽车如何改变城市生活?听听他们怎么说

    无人驾驶汽车如何改变城市生活?听听他们怎么说

网友点评网友点评
阅读推荐阅读推荐

据国外媒体报道,在过去两年内,聊天机器人(chatbot)、人工智能以及机器学习的研发和采用取得了巨大进展。许多初创公司正利用人工智能和...

霍金 视觉中国 图 英国著名物理学家霍金(Stephen Hawking)再次就人工智能(AI)发声,他认为:对于人类来说,强大AI的出现可能是最美妙的...

文|郑娟娟 今年,人工智能(AI) 60岁了。在AI60岁的时候,笔者想要介绍一下AI100,一个刚刚2岁的研究项目,但它的预设寿命是100年,甚至更长...

AlphaGo与李世石的人机大战,为大众迅速普及了人工智能的概念。 但对谷歌而言,除了下围棋,现在的人工智能进展到哪一步了?未来,人工智能...