C语言递归课件.ppt

7.6 函数的递归调用 在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归调用。Ｃ语言的特点之一就在于允许函数的递归调用。例如： int f（int x） ｛int y，ｚ； ｚ＝f（y）； return（2*ｚ）； ｝ 在调用函数f的过程中，又要调用f函数，这是直接调用本函数，见图7.9。下面是间接调用本函数。 在调用f1函数过程中要调用f2函数，而在调用f2函数过程中又要调用f1函数，这两种递归调用都是无终止的自身调用。显然，程序中不应出现这种无终止的递归调用，而只应出现有限次数的、有终止的递归调用，这可以用if语句来控制，只有在某一条件成立时才继续执行递归调用，否则就不再继续。 例7.7 有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2。 即 age（5）＝age（4）＋2 　　age（4）＝age（3）＋2 　　age（3）＝age（2）＋2 　　age（2）＝age（1）＋2 　　age（1）＝10 　　可以用式子表述如下： 　　age（n）＝10　　　　（n＝1） 　　age（n－1）＋2　　 （n＞1） 可以看到，当n＞1时，求第n个人的年龄的公式是相同的。因此可以用一个函数表示上述关系。图7.11表示求第5个人年龄的过程。 图7.11 从图可知，求解可分成两个阶段：第一阶段是“回推”，即将第n个人的年龄表示为第（n－1）个人年龄的函数，而第（n－1）个人的年龄仍然不知道，还要“回推”到第（n－2）个人的年龄……直到第1个人年龄。此时age（1）已知，不必再向前推了。 然后开始第二阶段，采用递推方法，从第1个人的已知年龄推算出第2个人的年龄（12岁），从第2个人的年龄推算出第3个人的年龄（14岁）……一直推算出第5个人的年龄（18岁）为止。也就是说，一个递归的问题可以分为“回推”和“递推”两个阶段。要经历许多步才能求出最后的值。显而易见，如果要求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件。例如，age（1）＝10，就是使递归结束的条件。 #include stdio.h int age (int n) { int c; if(n==1) c=10; else c=age(n-1)+2; return(c); } main函数中只有一个语句。 从图7.12可以看到：age函数共被调用5次，即age（5）、age（4）、age（3）、age（2）、age（1）。其中age（5）是main函数调用的，其余4次是在age函数中调用的，即递归调用4次。请读者仔细分析调用的过程。应当强调说明的是在某一次调用age函数时并不是立即得到age（n）的值，而是一次又一次地进行递归调用，到age（1）时才有确定的值，然后再递推出age（2）、age（3）、age（4）、age（5）。请读者将程序和图7.11、图7.12结合起来认真分析。 例　7.8用递归方法求n！。 求n！··也可以用递归方法，即5！等于4！×5，而4！＝3！×4…1！＝1。可用下面的递归公式表示： n！＝1（n＝0，1） n·（n－1）！（n＞1） #include stdio.h float fac(int n) { float f; if(n0) { printf(n＜0，data error！); f=-1; } else if(n==0||n==1) f=1; else f=fac(n-1)*n; return(f); } 例7.9hanoi（汉诺）塔问题。这是一个古典的数学 问题，是一个只有用递归方法（而不可能用其他方法）解决的问题。问题是这样的：古代有一个梵塔，塔内有3个座A、B、C，开始时Ａ座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从Ａ座移到Ｃ座，但每次只允许移动一个盘，且在移动过程中每3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用Ｂ座，要求编程序打印出移动的步骤。 (1) 命令第2个和尚将63个盘子从A座移到B座； (2) 自己将1个盘子（最底下的、最大的盘子）从A座移到C座； (3) 命令第2个和尚将63个盘子从