再上一篇:第五章 函数与编译预处理
上一篇:5.2 函数的形参、实参、返回值及函数的原型说明
主页
下一篇:5.4 作用域和存储类
再下一篇:5.5 内联函数
文章列表

5.3 函数的嵌套与递归调用

《VC++程序设计基础》,讲述C++语言的语法和标准库,以及Visual C++ 函数库和MFC类库的使用,并附相关代码示例。

在C++语言中,在定义一个函数时,不允许在其函数体内再定义另一个函数,任一函数的定义均是独立的。函数之间都是平等的、平行的。函数之间的嵌套调用是可以的,即在调用一个函数时,在该函数的函数体内又调用另一个函数。当在一个函数A的定义中出现调用函数A的情况时,或在A函数的定义过程中调用B函数,而在B函数的定义过程中,又调用了A函数。这种调用关系称为递归调用。前一种情况称为直接递归,而后一种情况称为间接递归。在C++语言中, 这二种递归调用都有是允许的。我们举例子来说明之。

例 5.4 求阶乘: 5! 和10!

分析:可有二种解决办法,一种是已知1的阶乘为1,2!=1!*2,由2!又可求出3!,依次类推,分别可求出5!和10!。这种方法是递推的方法。另一种方法是,将n!可以定义为:

1 n=0

n!= 1 n=1

n*(n−1)! n>1

即求n!的问题可变成求n*(n-1)!,这又成为一个求(n-1)!的问题。同样地,(n-1)!的问题又可以成为一个求(n-2)!的问题;依次类推,直到成为求1!或0!的问题。根据定义,1!或0!为1。这就是递归的方法。对于递归的方法,必须分析清楚三方面的问题:首先是递归的公式,在本例中为n*(n-1)!;第二是递归的结束条件,本例中是0或1的阶乘为1;第三是约束条件,即限制条件,本例为n必须大于或等于0。本例的递归程序如下:

#include

long int f( int n)

{

if ( n == 0 || n == 1 ) return ( 1); //A

else return n * f( n-1 ); //B

}

void main(void)

{

cout<< "5! = " << f(5) << "10!= " << f(10) << '\n';

}

在设计递归程序函数时,通常是先判断递归结束条件,再进行递归调用。如本例中,先判别n是否等于0或1,若是,则结束递归;否则,根据递归公式进行递归调用。

递归函数的执行过程是比较复杂的,都存在连续递归调用(参数入栈)和回推的过程。我们以函数调用f(5)来说明递归函数的执行过程。因f(5)中参数不为1,故执行该函数中的B行,即成为5*f(4);同理,f(4)又成为4*f(3);依次类推,直到出现函数调用f(1)时,则执行函数中的A行,将值1返回。这就是图5.2中左边的连续递归调用过程。

5*f(4) 5*24=120

4*f(3) 4*6=24

3*f(2) 3*2=6

2*f(1) 2*1=2

1

图 5.2 递归和回推过程

对于本例,当出现函数调用 f(1)时,递归结束,进入回推的过程。将返回值1与2相乘后的结果作为f(2)的返回值,与3相乘后,结果值6作为f(3)的返回值,进行回推。图5.2中右边的从底向上给出了回推过程。

例 5.5 求Fibonacci数列的前40 个数,要求每行输出四个数。Fibonacci数列的递归公式为:

⎧ n=1

⎪1

⎪ n=2

f = ⎨1

n ⎪

f + f n>2

⎪ n−1 n−2

其中,递归公式的约束条件是n大于等于1。

当n的值较大时,Fibonacci数较大,所以必须用长整数或实数来表示。

程序为:

#include

#include

long int f(int n)

{

if ( n == 1 || n == 2 ) return (1);

else return f( n-1 ) + f( n -2 );

}

void main(void )

{

int i ;

for ( i = 1 ; i <= 40 ; i ++) {

cout <

if ( i % 4 == 0 ) cout << "\n";

}

cout << "\n";

}

注意:在使用递归的方法设计程序时,在递归程序中一定要有递归结束条件,否则在执行程序时,会产生无穷尽的递归调用。上面的二个例子,也可以用递推的方法来进行程序设计,即先初始化递推条件,再分别用一个循环语句来实现。对于同一个问题,可以使用递推或递归的方法来进行程序设计时,使用哪一种方法好呢?通常,使用递归的方法,程序简洁易懂;而使用递推的方法,程序的执行速度要快一些。关于如何将递归的的问题转换为递推或迭代的技术已超出本书讨论的范围,有兴趣的读者可参阅有关的资料。需要指出的是,并非是所有的递归问题都能转换成递推的方法来解决问题。最典型的例子是河内(Hanoi)塔问题,该问题只能用递归的方法来解决,而无法用递推的办法解决。

例 5.6 河内塔问题。

━━┻━━━ ━━━━━━ ━━━━━━

A柱 B柱 C柱

图 5.3 Hanoi塔问题

设A柱上有n个盘子,盘子的大小不等,大的盘子在下,而小的盘子在上,如图5.3所示。要求将A柱上的n个盘子移到C 柱上,每一次只能移一个盘子,在移动的过程中,可以借助于任一根柱子,但必须保证三根柱上的盘子都是大盘子在下,小盘子在上。要求编一个程序打印出移动盘子的步骤。

分 析:假定先将A柱上的n-1个盘子移到 B柱上;只要将A柱上的最后一个盘子移到C柱上;然后,再将B柱上的n-1个盘子移到 C柱上。即由原来要移动n个盘子的问题变成了移动n-1个盘子的问题。同样地,移动n-1个盘子的问题,又可以分解成移动n-2个盘子的问题,这是一个递归的过程。直到变成移动一个盘子的问题时,则递归结束。

根据以上的分析,将A柱上的n个盘子移到C柱上可分解为三个步骤:

1.将A柱上的n-1 个盘子借助于C柱先移到 B柱上;

2.将A柱上的最后一个盘子直接移到C柱上;

3.再将B柱上的n-1个盘子移到C柱上。

其中,第一步又可以分解为:

1.1将A柱上的n-2个盘子借助于B柱先移到C柱上;

1.2将A柱上的第n-1个盘子直接移到B柱上;

1.3再将C柱上的n-2个盘子移到B柱上。

这种分解可以一直递归地进行下去,直到变成移动一个盘子时,递归结束。以上的三个步骤可以分为二类操作:

第一个是将 m(m>1)个盘子从一根柱移动到另一根柱,这是一个递归的过程。第二个操作是将一根柱上的一个盘子移动到另一根柱上。

我们分别编写二个函数来实现以上的二个操作。递归函数 hanoi( int n,char A, char B ,char C)实现把A柱上的n个盘子移到C柱上,而函数move ( chara, char b)输出移动盘子的提示信息。程序为:

#include

void move ( char a, char b)

{

cout << " Move " << a << " to " << b << " \n";

}

void hanoi( int n, char A, char B ,char C)

{

if ( n == 1 ) move ( A,C);

else {

hanoi ( n-1 ,A , C, B);

move ( A , C);

hanoi ( n-1 ,B , A , C);

}

}

void main( void )

{

int n ;

cout << "Input number of plates!";

cin >> n;

cout << "\n";

hanoi( n, 'A' ,'B' ,'C');

}