C语言递归编程实例-C语言程序设计

在调用一个函数的过程中又出现了直接或者是间接地调用该函数本身,这称为函数的递归调用。C语言允许函数的递归调用。

例如,有函数f如下:

这个函数是一个递归函数。在调用函数f的过程中,又要调用f函数,这是直接调用本函数,结构如图5-1所示。

C语言的特点之一就在于允许函数递归调用。例如,在调用f1函数的过程中,又出现了调用f1函数,这称为直接递归调用,而在调用fl函数过程中出现了调用f2函数,又在调用f2函数过程中出现了调用f1函数,这称为间接递归调用,如图5-2所示。但是运行该函数将无休止地调用其自身,这当然是不正确的。为了防止递归调用无终止地进行,必须在函数内有终止递归调用的手段。常用的办法是加条件判断,满足某种条件后就不再作递归调用,然后逐层返回。

图5-1　函数直接调用

图5-2　函数间接调用

一般来说,能够用递归解决的问题应该满足以下3个条件。

(1)需要解决的问题可以化为一个或多个子问题来求解,而这些子问题的求解方法与原来的问题完全相同,只是在数量规模上不同;

(2)递归调用的次数必须是有限的;

(3)必须有结束递归的条件(边界条件)来终止递归。

思考:4!等于3!×3,而3!＝2!×3…1!＝1。

定义函数

则有

已知(www.xing528.com)

可以看到,当n＞1时,求n的阶乘公式都是一样的。因此可以用函数表示上述关系。图5-3表示了求4的阶乘的过程。

图5-3　递归层次

从图可知,求解分为两个阶段:第一阶段是“回推”,即将n!的阶乘表示为(n－1)!的函数,而(n－1)!仍不知道,还要继续“回推”到(n－2)!……直到0!,此时0!的阶乘是已知的,不用再向前推了。然后是第二阶段,采用递推方法,从0!推知1!,从1!的阶乘推知2!……直到推知4!。也就是说递归问题可以分为“回推”和“递推”两个阶段。要经历若干步才能求出最后的值。如果要求递归过程不是无限制地进行下去,必须具有一个结束递归过程的条件,如f(0)＝0,就是递归结束的条件。

其程序如下:

函数的递归调用过程如图5-4所示。

图5-4　函数递归和返回过程

其中main函数调用f函数一次,其余是在f函数中调用的,调用4次。请读者分析调用过程。另外请考虑如果输入20或者10,求20的阶乘或者10的阶乘,请观察输出结果。

程序运行结果:

请输入一个正整数:10

10!＝3628800

通过分析可以看出,递归调用的过程可分为两个阶段。

第一阶段称为“递推”阶段:将原问题不断化为新问题,逐渐从未知的方向向已知的方向推测,并最终达到已知的条件,即递归结束条件。第二阶段称为“回归”阶段:该阶段是从已知条件出发。按“递推”的逆过程,逐一求值回归,最后到递推的开始之处,完成递归调用。可见,“回归”的过程是“递推”的逆过程。在递归过程中,当函数自己调用自己时,系统将自动把函数中当前的变量和形参暂时保留起来,在新一轮的调用过程中,系统为新调用的函数所用到的变量和形参开辟另外的存储单元(内存空间)。每次调用函数所使用的变量在不同的内存空间,且递归调用的层次越多,同名变量占用的存储单元也就越多。可见递归虽然可使程序容易编制,可读性强,在算法上简单,代码紧凑,但它并不节省空间,运行效率不高,并且无条件的递归往往引起需要的存储空间超过实际可能而导致运行失败。所以一个正确的递归必须保证递归过程是有限的。