前言 说白了递归就象我们讲的那个故事：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：……也就是直接或间接地调用了其自身。 就象上面的故事那样，故事中包含了故事本身。因为对自身进行调用，所以需对程序段进行包装，也就出现了函数。 函数的利用是对数学上函数定义的推广，函数的正确运用有利于简化程序，也能使某些问题得到迅速实现。对于代码中功能性较强的、重复执行的或经常要用到的部分，将其功能加以集成，通过一个名称和相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行简单调用就能来完成特定功能。 例如我们把上面的讲故事的过程包装成一个函数，就会得到： void Story() {     puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：");     getchar();//按任意键听下一个故事的内容     Story(); //老和尚讲的故事，实际上就是上面那个故事 } 函数的功能是输出这个故事的内容，等用户按任意键后，重复的输出这段内容。我们发现由于每个故事都是相同的，所以出现导致死循环的迂回逻辑，故事将不停的讲下去。出现死循环的程序是一个不健全的程序，我们希望程序在满足某种条件以后能够停下来，正如我们听了几遍相同的故事后会大叫：“够了！”。于是我们可以得到下面的程序： #include<stdio.h>   const int MAX = 3;   void Story(int n);//讲故事   int main(void) {     Story(0);            getchar();     return 0; }   void Story(int n) {     if (n < MAX)     {         puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说了一个故事：");         getchar();         Story(n+1);     }     else     {         printf("都讲%d遍了！你烦不烦哪？\n", n);         return ;     } } 上面的Story函数设计了一个参数n，用来表示函数被重复的次数，当重复次数达到人们忍受的极限（MAX次）时，便停下来。   基本递归     数学归纳法表明，如果我们知道某个论点对最小的情形成立，并且可以证明一个情形暗示着另一个情形，那么我们就知道该论点对所有情形都成立。     数学有时是按递归方式定义的。 例1：假设S（n）是前n个整数的和，那么S（1）= 1，并且我们可以将S（n）写成S（n）= S（n-1）+ n。     根据递归公式，我们可以得到对应的递归函数： int S(int n)    //求前n个整数的和 {     if (n == 1)         return 1;     else         return S(n-1) + n; }     函数由递归公式得到，应该是好理解的，要想求出S（n），得先求出S(n-1)，递归终止的条件（递归出口）是(n == 1)。     再举一个典型的例子：斐波那契(Fibonacci)数列。 例2：斐波那契数列为：1、1、2、3、5、8、13、21、…，即 fib(1)=1; fib(2)=1;  fib(n)=fib(n-1)+fib(n-2) (当n>2时)。     我们曾经用迭代法解决了这个问题，实际上数列公式本身是一个递归公式，如果用递归算法来解将更自然。根据递归公式，很容易递归函数： int Fib(int n) {     if (n < 1)//预防错误         return 0; if (n == 1 || n == 2)// 递归出口         return 1;             return Fib(n-1) + Fib(n-2); }       注意：尽管Fib似乎是在调用自身，但实际上它在调用自身的一个副本。该副本是具有不同参数的另一个函数。任何时候只有一个副本是活动的，其余的都将被挂起。递归实现要求进行某种簿记工作来跟踪挂起的递归调用，如果递归调用链非常长，计算机就会耗尽内存。 实际在上例中，当n = 40时，程序将变得缓慢，当n再大一些，内存就不够了。     不用说,这种特例不能说明递归调用是最佳的调用，因为问题如此简单，不用递归也能解决。大多数恰当使用递归的地方不会耗尽计算机内存，只是比非递归耗费稍多时间。但是，递归一般可以得到更紧凑的代码。      在实际编程中，有许多定义或者问题本身就具有递归性质。所以我们顺其自然就想到用递归来解决，这样不仅代码少,而且结构清晰。但是问题是我们应该怎样设计递归呢？这确实一个问题。由于许多问题并不是很明显的表现出递归的关系，所有很大一部分需要我们进行推导，从而得出递归关系，有了递归关系，编写代码就相对的比较简单了。 首先,我们了解递归算法的特点，所谓的递归，就是把一个不能或不好直接求解的“大问题”转化成一个或几个与原问题相似的“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决（此时分解到递归出口）。在逐步求解“小问题”后，再返回得到“大问题”的解。 因此，递归的执行过程由分解和求值两部分构成。首先是逐步把“大问题”分解成形式相同但规模减小的“小问题”，直至分解到递归出口。一旦遇到递归出口，分解过程结束，开始求值过程，所以分解过程是“量变”过程，即原来的“”大问题”在慢慢变小，但尚未解决。遇到递归出口后，便发生了“质变”，即原递归问题转换成直接问题。 由于递归只需要少量的步骤就可描述解题过程中所需要的多次重复计算，所以大大的减少了代码量。递归算法设计的关键在于，找出递归方程和递归终止条件(又叫边界条件或递归出口)。递归关系就是使问题向边界条件转化的过程，所以递归关系必须能使问题越来越简单，规模越小。一定要知道，没有设定边界的递归是只能‘递’不能‘归’的，即死循环。 因此,递归算法设计，通常有以下3个步骤： 1. 分析问题，得出递归关系。 2. 设置边界条件，控制递归。 3. 设计函数，确定参数。 我们来看一个简单的应用。 例3：楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法。例如，当n=3时，共有3种走法，即1+1+1，1+2，2+1。 算法分析：设n阶台阶的走法数为f(n)，显然有： 1                 n = 1  f(n) = {  2                 n = 2 f(n-1) + f(n-2)   n > 2   得到相应的函数如下： int F(int n) {     if (n == 1 || n == 2)         return n;       return F(n-1) + F(n-2); } 例4：整数划分的问题：对于一个整数n的划分，就是把n表示成一系列的正整数的和的表达式，注意划分与次序无关. 例如,6可以可以划分为： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1 现在问题是,给一个n求他的所有划分. 这个问题初看,很难找出大规模问题与小规模问题之间的关系,我们注意了,对于上面的第一行,所有加数不超过6,第2行, 所有加数不超过5,.....第6行所有加数不超过1.因此,我们可以定义一个q(n, m)的函数,表示 n所有加数不超过m的划分数目.所以n的划分总数目可以表示为q(n, n).那我们怎样才能把找出q(n, n)的递归关系呢? 很显然,我们可以立即得到以下关系, q(n,n) = q(n,n-1) + 1; 所以问题规模变小，但是我们很不能根据这个关系转化为更小的问题，所以我们主要考虑这种情况：q(n, m)（其中m < n），怎样把这中情况分解呢。我们尝试的把q(n, m)变为q(n, m-1)；我们惊奇的发现，只要把q(n, m-1)加上包含加数m的项就等于q(n, n)，即q(n, m) = q(n, m-1) + 包含m加数的表达式数。例如m = 4，我们可以把q(n, 4) = q(n, 3) + 2(包含4加数的表达使有两个:4+2, 4+1+1)。而我们发现，包含4的表达可以转化为q(n-4, 4) (想想？)，所以的递归关系式就出来了： q(n，m) = q(n，m-1) + q(n-m，m)； 接下来就是找边界条件了，我们知道当n = 1时，q(n, n) = 1；当m =1时，q(n, m) = 1；有了边界条件,我们递归基本上完成了.得到递归公式：              1,                           n = 1, m = 1; q(n，m) = {  q(n，n),                     n < m;              1 + q(n, n-1),               n = m;              q(n，m-1) + q(n-m，m),       n > m > 1. 编写代码如下: #include<stdio.h>   int F(int n,int m);   int main() {     int i;         for (i=1; i<21; i++)         printf("%d - %d\n", i, F(i, i));             getchar();     return 0; }   int F(int n, int m) {     if (n == 1 || m == 1)//递归出口         return 1;         if (n == m)         return F(n, n-1) + 1;     else if (n < m)         return F(n, n);     else         return F(n, m-1) + F(n-m, m); }   例5：Hanoi塔问题：设A，B，C是3个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自上而下，由小到大地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座A上的这一叠圆盘移到塔座C上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 1．每次只能移动1个圆盘； 2．任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 3．在满足移动规则1和2的前提下，可将圆盘移至A，B，C中任一塔座上. 算法分析：这是一个典型的适合用递归算法来解决的问题。试想要把n个盘子从柱A移到柱C上，则必须先把上面n-1个盘子从柱A全部移到柱B，然后把第n个盘子由柱A移到柱C ，再把柱B上的n-1个盘子全部移到柱C。这样就把移动n个盘子的问题变成了移动n-1个盘子的问题，如此不断减小递归的规模，直到递归出口。递归的边界条件是，当n == 1时，直接把它由柱A移到柱C。 #include<stdio.h>   void Hanoi(int n, char a, char b, char c); //移动汉诺塔的主要函数   int main(void) {       int n = 4;             Hanoi(n, 'A', 'B', 'C');         getchar();       return 0; }   void Hanoi(int n, char a, char b, char c)//汉诺塔，把柱A所有的盘子移到柱C {     if (n == 1)//如果只有一个盘子，直接由柱A移到柱C         printf("Move disk from %c to %c\n", a, c);     else     {         Hanoi(n-1, a, c, b);//先把上面n-1个盘子从柱A全部移到柱B         printf("Move disk from %c to %c\n", a, c);//再把第n个盘子由柱A移到柱C          Hanoi(n-1, b, a, c);// 再把柱B上的n-1个盘子全部移到柱C     } }     从上述的例子中我们可以发现，递归算法具有以下三个基本规则： 基本情形：至少有一种无需递归即可获得解决的情形，也即前面说的边界条件。 进展：任意递归调用必须向基本情形迈进，即前面所说的使得问题规模变小。 正确性假设：总是假设递归调用是有效的。递归调用的有效性是可以用数学归纳法证明的，所以当我们在设计递归函数时，不必设法跟踪可能很长的递归调用途径（比如Hanoi塔问题）。这种任务可能很麻烦，易于使设计和验证变得更加困难。所以我们一旦决定使用递归算法，则必须假设递归调用是有效的。

评论