理解递归程序设计

递归是指函数在执行的过程中调用到自身已完成需要的功能，用递归能解决的问题通常能将问题不断缩小为性质相同但规模更小的问题（递归情况），直到问题足够小能够直接解决（基本情况），如下面简单的例子：

#include

void f(int n)

{

   printf("Level %d:n location %p\n",n,&n); /* 语句1 */

   if(n < 3)

       f(n+1); 

   printf("Level %d:n location %p\n",n,&n); /* 语句2 */

}

int main(void)

{

  f(1);

  return 0;

}

 

/*  输出结果  */
Level 1:n location 0240FF48     #1
Level 2:n location 0240FF28     #2
Level 3:n location 0240FF08     #3
Level 3:n location 0240FF08     #4
Level 2:n location 0240FF28     #5
Level 1:n location 0240FF48     #6

 

从运行结果可以看出，每一级的递归都使用它自己的私有的变量n，具体的调用流程如下：

（从左到右为时间顺序，从上到下位执行层次）

f(1)

    #1  f(2)                                  #6【f(1)返回】

                #2  f(3)               #5 【f(2)返回】    

                           #3   #4 【f(3)返回】

   

                 

递归的基本原理及特性：

1． 每一次函数调用都会有一次返回．当程序流执行到某一级递归的结尾处时，它会转移到前一级递归继续执行。

2． 递归函数中，位于递归调用前的语句和各级被调函数具有相同的顺序．如打印语句1位于递归调用语句前，它按照递归调用的顺序被执行了3次。

3． 每一级的函数调用都有自己的私有变量。

4． 递归函数中，位于递归调用语句后的语句的执行顺序和各个被调用函数的顺序相反。如打印语句2位于递归调用语句后，它按照递归调用的相反顺序被执行了3次。

5． 虽然每一级递归有自己的变量，但是函数代码并不会得到复制。

6． 递归函数中必须包含可以终止递归调用的语句．

 

实例：使用递归输出指定序列的全排列

 

问题分析：全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。现以{1, 2, 3, 4, 5}为 例说明如何编写全排列的递归算法。

 

1． 首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列，由于一个数的全排列就是其本身，从而得到以上结果。

2． 再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合。

3． 从而可以得出，设一组数p = {r1, r2, r3, ... ,rn}, 全排列为perm(p)，pn = p - {rn}。

 

因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)（递归情况，将问题分成了n个子问题）。当n = 1时perm(p) = r1(基本情况)。 即将整组数中的所有的数分别与第一个数交换，然后对每种交换的情况处理后面n-1个数全排列的情况。

 

全排列的递归实现参考代码如下：

#include

 

void swap(int num[], int i, int j)

{

    int tmp = num[i];

    num[i] = num[j];

    num[j] = tmp;

}

 

void perm(int num[],int k,int m)

{

    int i;

    if(k==m)

    {

         for(i=0;i<=m;i++)

            printf("%d ",num[i]);

         printf("\n");

    }

 

    for(i=k;i<=m;i++)

   {

        swap(num, k, i);

        perm(num,k+1,m);

        swap(num, k, i);

   }

}

 

int main()

{

    int num[] = {1, 2, 3, 4};

    perm(num, 0, 3);

    return  0;

}