基于C语言的递归与循环关系的研究

摘要本文阐述了作者对于算法设计中递归问题和循环问题的理解,同时讨论了两者间的转换关系,并使用C语言对其中一种转换方式进行了实验,以求在相关算法的优化设计方面能够有所提高。

关键词递归 循环 C语言

中图分类号:TP31文献标识码:A

递归作为一种正对实际问题的程序设计解决方案,在整个编程语言学习及程序设计方面有着极其重要的地位。而在实际的教学环节中对于这样一种具有很高使用价值的编程技术,在讲解上和学生理解上还存在着一定困难。

循环结构是结构化程序设计的三种结构之一,主要应用在处理某些需要重复执行特定语句的情况下,通常在使用循环时我们需要明确三个重要条件:

1> 循环的初始条件;

2> 循环的中止条件(或在什么情况下循环运行);

3> 程序有趋于结束的趋势。

而递归作为一种算法,在数学上我们时这样定义它的,以n的阶乘为例:

0!=1(*)

n!=n*(n-1) 当n>0时 (**)

其中(*)称为基本实例(基本实例的值必须是直接获得的);(**)称为递归归约。递归被定义为:自身定义为一种含有自身简化的形式。那么从形式上我们可以清楚的看到:

1> 每个递归定义必须有一个(或者多个)基本实例;

2> 递归归约最终归结到基本实例;

3> 在基本实例处停止递归。

从中我们不难发现递归的算法形式条件和循环的条件是非常类似的。

那么在运行递归函数时,逻辑上我们可以认为递归函数有无限的自身拷贝(当然这是受限的),完成某个递归调用后,控制返回到先前的调用环境。这同循环算法在思想上也是异曲同工的。所以我们也完全可以编写一个循环结构来替代递归。

造成这种可替代性的主要原因是因为目前为止的编译系统处理递归函数时,在编译之后都是自动将递归转化为循环的。但是和循环不同的是,编译后的递归需要创建一个内存栈来存储递归过程中的临时变量,对于递归函数的调用和返回操作,则分别对应栈的入栈和出栈。

因此任何一个递归程序都可以通过引入堆栈的形式来转化为循环,这种转化其实就是模拟计算机实现递归的过程。你可以考虑人脑来计算递归的过程:先倒过来向前递归,到达最初点以后再正过来向后递推,堆栈的作用就是记住过程中的临时变量。虽然这样做只不过是模拟递归的执行过程,将原来由编译器实现的事情在程序中用代码实现了一遍,但是确实可以通过循环和堆栈的数据结构特性来实现递归的算法和递归函数的功能。

那么基于递归和循环的这种可以相互替代性,我们应当如何选用递归或循环呢?

在大多数编译系统中递归会受栈(编译系统自动分配)的大小限制,如果递归调用的次数很多,就不能使用递归了。一般情况下,递归效率不如循环高,主要是保存栈需要时间,调用函数也需要时间,再加上开辟栈的额外内存开销,从而导致程序性能的降低。递归一般在算法或者数学模型是递归定义的情况下,为了方便编码(主要是理解)才使用。但是我们也应该注意到,依靠栈和循环来模拟递归,在技术上可行,但在提高程序性能上,意义并不明显(两者在编译后,代码几乎完全一样)。只有使用真正意义上的非递归算法才能够在本质上与递归区别开。

这里所谓的非递归算法就是指不引入堆栈等辅助空间进行计算的算法。更确切地说,非递归是指辅助的空间为0或1的算法(即辅助空间的规模和问题的输入规模无关)。但是很遗憾,在目前可计算性理论发展的水平下事实上,一般只能对尾递归或单向递归的情形,都可利用循环的方法,将递归算法改为非递归算法。

当然,另外还有很多方法将递归转化为递推,例如利用Cooper变换和拓广Cooper变换:

[Cooper变换]

输入模式:

f(x) ≡ if b(x) then h(x)

else F(f(k(x)), g(x))

输出模式:

f(x) ≡ G(x, e)

G(x, y) ≡ if b(x) then F(h(x), y)

else G( k(x), F(g(x),y) )

其中:

x, k: TYPE1, k(x) -< x( 符号 -< 表示偏序)

y, G, h, g, f, F: TYPE2

b: boolean

e: F的右单位元,即F(x, e) = x

可用性条件:

(1)F满足结合律,即F(F(x,y),z) = F(x, F(y, z))

(2)F有右单位元e;

(3)b, h, g, k中都不含f

[拓广的Cooper变换]

输入模式:

f(x) ≡ if b(x) then h(x)

else if b1(x) then F1( f( k1(x) ), g1(x) )

...

else if bn(x)then Fn( f( kn(x) ), gn(x) )

else F0( f( k0(x) ),g0(x) )

输出模式:

f(x) ≡ if b(x) then h(x)

else if b1(x) then G1( k1(x), g1(x) )

...

else if bn(x) then Gn( kn(x), gn(x) )

else G0( k0(x), g0(x) )

对于所有的 0≤i≤n,

Gi( x, y) = if b(x) then Fi( h(x), y )

else if b1(x) then Gi( k1(x), F1( g1(x), y ) )

...

else if bn(x) then Gi( kn(x), Fn( gn(x), y ) )

else Gi( k0(x), F0( g0(x), y ) )

其中:

对于所有的 0≤i≤n

x, ki: TYPE1, ki(x) -< x ( 符号-< 表示偏序)

gi, h, Fi, Gi, y: TYPE2

b, bj: boolean, 1≤j≤n

b(x)∧b1(x)∧……∧bn(x) = (空集)

b(x)∨b1(x)∨……∨bn(x) = (全集)

可用性条件:

(1)Fi满足结合律,即Fi( Fj(x, y), z ) = Fj( x, Fi(y, z) ), 0≤i, j≤n

(2)b, bj, h, gi, ki中都不含f, 0≤i≤n, 1≤j≤n

以及T1,T2变换,C变换,RR变换等等,在组合数学理论中已经研究的比较多了。也不再是本文的重点。对此有兴趣的读者可以阅读一下参考书目(2)的第三章和第五章。

综上所述,递归和循环无论在算法上还是在实现上都有着巨大的联系,如采用栈的方法则可以实现所有递归和循环的转换,但是如果只采用非递归算法的循环,则只能够处理原始递归和一些可计算性较大的递归函数。

参考文献

[1][美] Robert Sedgewick.C算法(第一卷).人民邮电出版社,ISBN0-201-31452-5.

[2][美] Kennety H.Rosen.离散数学及其应用.机械工业出版社,ISBN7-111-07577-3.

[3][美] Richard A Brualdi.组合数学.机械工业出版社,ISBN7-111-07569-2.

[4][美] Alfred V.Aho.数据结构与算法.清华大学出版社,ISBN7-302-07564-6.

推荐访问： 递归 循环 语言 关系 研究