C语言程序设计：递归示例

递归程序设计是一个非常有用的方法,可以解决一些用其他方法很难解决的问题,任何一个递归调用的应用程序必须包括两部分:①递归循环继续的过程;②递归调用结束的过程。

递归函数的形式一般如下:

　return递归函数调用返回的结果值;

递归程序在设计过程中的技巧性要求比较高,对于一个具体的问题,如果希望写出递归程序,首先要归纳出递归公式,并不是所有的递归都像求阶乘问题那样简单,如求解两个数的最大公约数,两个数的最大公约数是能够整除这两个整数的最大整数。求最大公约数的最经典的算法是欧几里得算法,又称辗转相除法。可以用gcd(a,b)表示两个数的最大公约数。辗转相除法是利用以下性质来确定两个数的最大公约数的。

如果a/b的余数r不为0,则gcd(a,b)＝gcd(b,r);

a和a的倍数之最大公约数为a。

通过递归式子可以很容易写出以下递归函数:

当余数为0时,不再执行递归函数,可以认为是整个递归函数的出口。

【例5-10】进制转换问题。

问题描述:输入一个十进制整数n,输出对应的二进制整数。常用的转换方法为“除2取余,倒序排列”。将一个十进制数除以2,得到余数和商,将得到的商再除以2,依次类推,直到商等于0为止,倒取除得的余数,即为所求的二进制数。可以看出其是一个逐步缩小原问题规模的递归过程,可以采用递归函数实现,在输出余数的过程中,因为要到取,故应该在递归退出时打印出其余数。

例如,把52换算成二进制数52除以2得到的余数依次为0、0、1、0、1、1,倒序排列,得到52对应的二进制数110100。

代码:

在进制转换问题中,可以用递归方法实现,当商为0时,不再递归,而是打印此时的余数,之后层层返回到上一层调用函数的函数体内,倒序打印余数。读者也可用其他方法实现,如利用堆栈等,但是在有些实际问题中,只能用递归算法才能实现。典型的问题是Hanoi塔问题。

【例5-11】Hanoi塔问题。

相传在古代印度的Bramah庙中,有位僧人整天把3根柱子上的金盘倒来倒去,原来他是想把64个一个比一个小的金盘从一根柱子上移动到另一根柱子上去。移动过程中恪守下述规则:每次只允许移动一只盘子,且大盘不得摞在小盘的上面,如图5-5所示。

图5-5　左侧为A，中间为B，右侧为C

有人会觉得这很简单,然而真的动手移动盘子就会发现,如果以每秒移动一个盘子计算,按照上述规则将64个盘子从一根柱子移至另一根柱子上,所需时间约为5800亿年。

怎么样编写程序?先从最简单的情况分析起,试着搬搬看,慢慢理出思路。

(1)在A柱子上有一个盘子,如图5-6所示。假定盘号为1,这时只需要将该盘从A柱直接搬至C柱,一次完成,记为move 1 from A to C。

图5-6　从A到C

(2)在A柱上有两个盘子,如图5-7所示,1为小盘,2为大盘。

图5-7　A上有两个圆盘

第一步,将1号盘从A移动到B,这是为了让2号盘能移动,记为move 1 from A to B;(www.xing528.com)

第二步,将2号盘从A移动到C,记为move 2 from A to C;

第三步,将1号盘从B移动到C,记为move 1 from B to C。

(3)在A柱上有3个盘子,如图5-8所示,从小到大分别为1号、2号、3号。

图5-8　A上有三个圆盘

第一步,将1号盘和2号盘视为一个整体。先将二者作为整体从A移至B,为3号盘可以移动到C上创造机会。这一步记为move(2,A,C,B),意思为将上面两个盘子作为整体从A借助于C移动到B上;

第二步,将3号盘从A移动到C上,一次到位,记为move 3 from A to C;

第三步,处于B上的作为一个整体的2个盘子,再移动到C上,这一步记为move(2,B,A,C),意思为将两个盘子作为整体从B借助于A移动到C上。

(4)从题目上的条件来看,大盘不允许摞在小盘上。在将1号和2号作为整体从A移动到B的过程中,move(2,A,C,B)实际上分解为3步。

第一步,move 1 from A to C;

第二步,move 2 from A to B;

第三步,move 1 from C to B。

经过上述三步,则可以将1号和2号圆盘作为整体从A移动到B上,为3号盘从A到C创造机会。当3号盘移动到C,则需要将1号和2号圆盘作为整体从B上移动到C。move(2,B,A,C)实际上也分为3步;

第一步,move 1 from B to A;

第二步,move 2 from B to C;

第三步,move 1 from A to C。

(5)move(2,A,C,B),是说要将2个盘子从A搬至B,没有C是不行的,因为先要将1号圆盘从A移动到C,给2号盘创造条件从A移动B,然后再把1号盘从C移动到B。

(6)定义搬移函数move(n,A,B,C),其物理意义是将n个盘子从A经B搬到C。

以上综合起来,可得到移动3个盘子的步骤为:

A→C,A→B,C→B,A→C,B→A,B→C,A→C。

共经历了7步。由此可以推出,移动n个盘子要经历2n－1步。

由上面的分析可知:将n个盘子从A座移动到C座可以分解为以下3个步骤:第一步,将A上n－1个盘子借助于C先移动到B上;

第二步,将A上的剩下的一个盘子移动到C上;

第三步,将n－1个盘子从B借助于A移动到C上。

上面的第一步和第三步中,都是把n－1个盘子从一根柱子移动到另一根柱子上,采取的办法是一样的,只是柱子的名称不一样。为使其一般化,可以将第一步和第三步表示为:将“one”柱子上的n－1个盘子移动到“two”(借助于“three”)。只是在第一步和第三步中,one、two、three、和A、B、C的对应关系不同。

第一步中,one对应A,two对应B,three对应C;第二步中,one对应B,two对应C,three对应A。

这显然是一种递归的定义,当再解决move(n－1,A,C,B)时又可以想到,用同样的方法移动。下面编写程序,分别用两个函数实现以上操作,用move(x,y)函数实现一个盘子从一根柱子移动到另外一根柱子的过程。hanoi(n,one,two,three)表示将n个盘子从“one”移动到“three”的过程(借助于C柱子)。程序如下:

在本程序中,调用了递归函数hanoi,其终止条件为hanoi函数的参数n的值等于1,显然,此时不再调用hanoi,直接执行move函数,move函数并未真正移动盘子,而是输出了移动圆盘的方案。