C语言——递归算法

C语⾔——递归算法

递归算法：是⼀种直接或者间接地调⽤⾃⾝的算法。在计算机编写程序中，递归算法对解决⼀⼤类问题是⼗分有效的，它往往使算法的描述

简洁⽽且易于理解。

递归过程⼀般通过函数或⼦过程来实现。

递归算法的实质：是把问题转化为规模缩⼩了的同类问题的⼦问题。然后递归调⽤函数(或过程)来表⽰问题的解。

递归算法解决问题的特点：

(1) 递归就是在过程或函数⾥调⽤⾃⾝。

(2) 在使⽤递归策略时，必须有⼀个明确的递归结束条件，称为递归出⼝。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运⾏效率较低。所以⼀般不提倡⽤递归算法设计程序。

(4) 在递归调⽤的过程当中系统为每⼀层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以⼀般不提倡⽤递

归算法设计程序。

递归的原理,其实就是⼀个栈(stack), ⽐如求5的阶乘,要知道5的阶乘,就要知道4的阶乘,4⼜要是到3的,以此类推,所以递归式就先把5的阶乘表

⽰⼊栈, 在把4的⼊栈,直到最后⼀个,之后呢在从1开始出栈, 看起来很⿇烦,确实很⿇烦,他的好处就是写起代码来,⼗分的快,⽽且代码简洁,其他

就没什么好处了,运⾏效率出奇的慢.

Wang Ding

1 / 6

Email：572645517@

Sunday, July 29, 2018 C语言递归

1 简介

递归，作为C语言最经典的算法之一，是一种非常有用的程序设计方法。虽然用递归算法编写的程序结构清晰，具有很好的可读性，还往往使某些看起来不易解决的问题变得容易解决。但在递归函数中，由于存在着自调用过程，程序控制反复进入其自身，使程序的分析设计有一定困难，致使很多初学者往往对递归迷惑不解，也在这上面花了不少的时间，却收效甚微。那么，究竟什么是递归?怎么实现递归呢?

所谓递归，简而言之就是在调用一个函数的过程中又直接或间接地调用该函数本身，以实现层次数据结构的查询和访问。

在函数中直接调用函数本身，称为直接递归调用。在函数中调用其它函数，其它函数又调用原函数，这就构成了函数自身的间接调用，称为间接递归调用。

2 条件

而采用递归方法来解决问题，必须符合以下三个条件：

1、 可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。说明：解决问题的方法相同，调用函数的参数每次不同（有规律的递增或递减），如果没有规律也就不能适用递归调用。

2、 可以应用这个转化过程使问题得到解决。说明：使用其他的办法比较麻烦或很难解决，而使用递归的方法可以很好地解决问题

3、 必定要有一个明确的结束递归的条件。说明：一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。

3 求n！问题

好知道是这样以后;我们来写一个众多教材上的程序：使用递归的方法求n!。

当n>1时，求n!的问题可以转化为n*(n-1)!的新问题。比如n=4：

第一部分：4*3*2*1 n*(n-1)!

第二部分：3*2*1 (n-1)(n-2)!

第三部分：2*1 (n-2)(n-3)!

第四部分：1 (n-4)! 4-4=0，得到值1，结束递归。

２００７年第５期　青海师专学报（教育科学）　

．『ｏＵＲＮＡＬ　ＯＦ　ＱＩＮＧＨＡＩ　ｊ『Ｉ　Ｒ　ＴＥＡＣＨＥＲＳ：ＣＯＬＬＥＧＥ　

ＩＥｄｕｃａｔｉｏｎ　Ｓｃｉｅｎｃｅ）　Ｎ０５．２００７　

文章编号：１００７—０１１７（２００７）０５－０１１８—０４　

例析程序设计中的递归算法　

刘萍　。黄小兰　

（１．青海民族学院计算机系，青海西宁８１０００７；２．青海民族学院教务处，青海西宁８１０００７）　

摘　要：递归算法是程序设计中的一种重要算法．用递归设计的程序结构比较清晰、简洁，但由于递归的设计思想比较巧　妙，特别是对于规模较大的问题，掌握递归的实现过程和算法的复杂度分析并不是一件容易的事．因此，本文通过具体实例详　细分析了递归算法的实现过程和复杂度，以此来加深对递归算法的进一步理解．　关键词：程序；递归算法；函数　中图分类号：ＴＰ３０１．４　文献标识码：Ｂ　

１　引言　在程序设计中，程序的执行效率与代码的可读性往往不可兼得．由于递归算法省略了程序设计中的许多　

细节操作　简化了程序设计过程．因此，在求解许多复杂问题时，采用递归使程序结构变得清晰、易读、层次感　

较强，但其缺点是程序执行过程中带来了附加的时间和空间上的耗费，而且运行效率会随着问题规模的增大　而下降．然而，随着当今计算机硬件的不断发展，程序结构简单、清晰、可读性强和易维护比运行效率更具有　

实际意义．因此，递归在程序设计中仍是一个很有用的设计方法，具有广泛的应用前景．　

２递归的含义　首先以求ｎ的阶乘为例，解释递归的含义．ｎ！看成ｎ　ｘ（ｎ一１）！，而把（ｎ一１）！看成（ｎ一１）Ｘ（ｎ－２）！，　

……，依次类推，直到最后０　１＝１为止，然后又顺次“递推”，求得ｎ！．因此，ｎ的阶乘可以表示成如下形式：　

ｎ　＝｛　×　ｎ一，　‘ｎ（　。　

显然，要求出５　１须求出４　１，要求出４　１须求出３　１，……，依次“回推”到已知的Ｏ！＝１即可，然后又顺次　

“递推”，就能等到５　１＝１２０．　《ｃ语言》、《ｃ＋＋语言》和《数据结构》等教材中明确定义：在调用一个函数的过程中又出现直接或间　

对C语言中递归算法的深入解析

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次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。