递归程序设计心得与体会

递归程序设计，用递归设计出来的程序总是简洁易读，极具美感。但是对于刚入门的学者来说，当遇到递归场景时，自己却难以正确的设计出合理的递归程序。博主曾经也是困惑不已，写的多了，也就渐渐的熟悉了递归设计。特谈一下自己的感受，有些术语是博主自己总结，有可能有不合理之处。

学习递归程序设计，建议首先应该从小规模的递归开始研究，小规模就是说自己可以调试跟踪代码，且自己不会晕。这个过程完成之后，才能熟练掌握递归层次之间的转换，明白递归的执行过程。在这里推荐一篇文章：http://blog.chinaunix.net/uid-20196318-id-31175.html，文章的第一个案例有一定的参考价值，第二个案例是全排列，将在后面讨论到。

在平时的程序设计中，遇到的递归问题一般可以分为两类，一类是过程递归，就是说执行的过程有明显的递归性，典型的就是求阶乘，斐波拉契数列，矩阵染色。。。大多数问题可以归结为第一类；第二类是结构递归，比如二叉树的各序遍历，链表逆转，反向打印等问题。两类问题的设计考虑是有所不同的，如果采用同样的思路去考虑两类不同问题，一定得不到正确的代码。建议从过程递归设计开始学习。

一、过程递归性

不管是过程递归还是结构递归首先要明确的就是一定要抛弃程序设计的细节，如果在设计过程中扣住细节，试图弄清楚每一步执行过程，你就失败了。递归设计的设计者首先要明确的是你的递归函数的功能，比如阶乘int fun(int n),他的功能就是返回n的阶乘，设计过程中要时时记住自己递归函数的设计目的。其次就是递归程序的出口设计，这一点是比较灵活的，不同问题有不同的设计;最后就是一定要有规模的递减。在整个递归设计过程中，一定要严格注意和把握这几点,缺一不可。

案例1：阶乘

阶乘基本就是递归入门级案例，现在将用上面的思路来设计。

1、设计出函数原型，明确其功能；

[cpp]  view plain  copy

1. int fun(int n)  //函数功能，返回n的阶乘结果  
2. {  
3.     /*设计递归出口，在这个程序中，出口明显是根据n的变化来确定的，而0！=0,1！=1，所以我们就以0或者1来结束递归*/  
4.     if(n==0||n==1)  
5.         return 1;  
6.     /*注意不要做任何的细节处理，明确你函数的功能,*/  
7.     //函数的功能是返回n的阶乘，那么直接就return fun(n);这样做可以吗？这样的话只做到了两点，没有规模的递减  
8.     /*要规模递减，只需做简单的处理*/  
9.     return n*fun(n-1);  
10.     /*那下面这个语句可以吗*/  
11.     /*return n*fun(n-1)*fun(n-2)，这样肯定是不可以的，时刻记住函数的功能，fun(n-1)代表n-1的阶乘，在乘以n-2的阶乘就不对了，可以这样写return n*(n-1)*fun(n-2),出口条件在改一下if(n<=1) return 1即可，因为1-2=-1判断条件出不来*/  
12. }  

2、矩阵染色

上面的案例其实我们并没有明显的感觉到过程的递归性，但这个下面的案例我们可以感觉到过程是有明显的递归性的。这个案例是小米2016招聘的一个笔试题，同时在2016中兴捧月比赛初赛中出现了一个极其类似的题。题目描述如下：对于一个矩阵，例如：

                                                              0 1 1 0

                                                              2 1 2 1

                                                              1 1 2 1

                                                              0 1 1 0

这个矩阵代表了一个图像，现在要给这个图像的指定位置染色，函数原型如下void fillwithcolor(int i,int j,int c),表示在图像的i，j位置和i，j位置临近的同色区域染色为c，注意：对角元素不算临近，对于上图如果调用fillwithcolor(1,1,5)的话，将得到下面的矩阵。

                                                              0 5 5 0

                                                              2 5 2 1  

                                                              5 5 2 1

                                                              0 5 5 0

由于 对角不算临近，所以第二排的最后一个1没有被染色。

对于这个问题，函数原型已经给出，void fillwithcolor(int i,int j,int c)把i,j位置以及相邻近位置染色为c，我们试想，由于不考虑对角的位置，所以我们只需要考虑上下左右的位置，对于满足要求的上下左右的位置是不是成为了新的i，j位置呢。只需要在新的位置调用函数即可.

[cpp]  view plain  copy

1. void fillwithcolor(int ** map,int i,int j,int c,int m,int n)//函数的功能是给i，j位置及其临近位置染色c,m,n表示矩阵的行数和列数。  
2. {  
3.     /*出口设计，出口设计是i，j位置总不可能跑到矩阵外面去了吧*/  
4.     if (i > m-1 || j > n-1)  
5.         return;  
6.     int temp = arr[i][j];  //先保存初始色  
7.     arr[i][j] = c;//染色  
8.    /*考虑往上面走的情况*/  
9.     if (i-1 >= 0)//不能走到图片外面去  
10.    {  
11.         if(map[i-1][j] == temp)  
12.         fillwithcocor(arr,i-1,j,m,n);//如果上面位置同色的话，也将上面的点染色c  
13.    }  
14.     /*考虑向下走的情况*/  
15.     if (i+1 <= m-1)//不能走到图片外面去  
16.    {  
17.         if(map[i+1][j] == temp)  
18.             fillwithcocor(arr,i+1,j,m,n);//如果上面位置同色的话，也将上面的点染色c  
19.    }  
20. /*向左和向右是同理的，在这里不做处理了*/  
21. /*.........................................................*/  

这个问题的过程是哟明显的递归性的，依次用同样的方法处理其上下左右的位置。

3、非波拉契数列

斐波拉契数列在这里不做介绍。

首先同样明确函数的目的

[cpp]  view plain  copy

1. int fei(int n)//返回非波拉契数列中第n个位置的元素  
2. {  
3.     /*设计出口，当位置为1或者2的时候，这两个位置上的数字都是1*/  
4.     if(n == 1|| n==2)  
5.         return 1;  
6.     /*同样做到规模有减小，不考虑任何细节，明确 递归函数的目的，fei(n-1)+fei(n-2)就是第n个位置的数，直接返回即可*/  
7.     return fei(n-1)+fei(n-2);  
8.     /*和阶乘的设计比起来，这个就更加的顺理成章，因为n位置上的数等于n-1位置上的加上n-2位置上的数，理所当然的同时也做到了     规模的递减*/  
9. }  

4、全排列问题

全排列递归程序设计是一个很好的理解递归设计的例子，有一定的难度。但是是很典型的递归程序设计案例，其过程有明显的过程递归性，下面将用上面的步骤来设计。

1、明确函数功能

我们假定传入的是一个数组，长度为n，递归函数初步设计成这样void permutation(int * arr,int n)，然后我们要明确的是全排列的具体递归过程，例如我们考虑1 2 3的全排列。

首先将1固定在排列首，然后求2 3的全排列，然后将2固定在排列首，求13的全排列，最后将3固定在排列首，求12的全排列。这是第一层递归，将1固定在排列首时候，对于2,3两个数构成的全全排列依然要重复上面的过程，即把2固定在首和把3固定在首，明显是一个递归的过程。如果我们所求的数组较长，加入1，2, 3，.....，n个数，我们就会依次求取2~n的排列，3~n的全排列，i~n的全排列，所以我们在设计函数的时候，需要加上一个参数m，代表m到n的全排列，所以函数的定义就如下void permutation(int *arr,int m,int n)函数的功能是求取数组第m个数到第n个数的全排列。

2、由于是求全排列，所以不建议用一个二维数组去保存所有的排列，打印出所有的全排列即可，为了便于理解，我们可以先不考虑出口，先来写代码。

[cpp]  view plain  copy

1. void permutation(int * arr,int m,int n)  
2. {  
3.     /*我们要一次完成让每一个数都当做一次排列的首，怎么做呢？当然是用循环*/  
4.     for(int i = 0;i < n;i++)  
5.    {  
6.         /*首先完成交换，交换完成之后就是求1，，，n的全排列了*/  
7.         swap(arr[i],arr[0]);  
8.                /*所以i+1*/  
9.         permutation(arr,i+1,n);  
10.         /*值得注意的是，我们在上面做了交换，试想一下，如果我们不把数组还原回来，还能不能做到让每个数都做一次排列首，显然          是不行的，交换完成之后，必须还原回来才行，所以有*/  
11.         swap(arr[i],arr[0]);  
12.     }  
13. }  

上面的代码已经初出具雏形，但是是不对的，为什么呢？因为毕竟是一个递归的过程，比如1234我们将1固定在排列首之后，后面的234依然要重复前面的过程，针对234也要做将2,3,4依次固定在234构成排列的排列首。所以上面的代码只考虑了第一层递归的交换，后面的都没考虑了，始终都是在和arr[0]座交换。上面函数中我们还有个参数m没用到，所以考虑用上。

[cpp]  view plain  copy

1. void permutation(int * arr,int m,int n)  
2. {  
3.     /*循环的目的是用于交换的*/  
4.     for (int i = m;i < n;i++)  
5.    {  
6.         /*k从0开始，表示第一个位置上的数，依次完成和k之后的数交换*/  
7.         swap(arr[m],arr[i]);   
8.         /*求除了第1,2,3，..，n个之后的数的全排列,m+1也存在了规模的递减*/  
9.         permutation(arr,m+1,n);  
10.         /*同样需要换回来*/  
11.         swap(arr[m],arr[i]);  
12.    }  
13.      /*考虑设计出口问题*/  
14.      /*m是不停的在向后游走的，n是长度，所以最后的位置是n-1，m不可能游到n-1之外去吧。所以其实m游走到n-1的位置时，恰好代表了完成了一次全排列的求解，再次声明，不要去考虑细节，整体上是合理的就是正确的*/  
15.        if(m > n-1)  
16.        {  
17.        /*这就是出口，当m到了n-1的位置时，表明以某个数为首的全排列计算完成，直接打印即可*/  
18.            for (int j = 0;j < n;j++)  
19.                cout << arr[j]<<" ";  
20.            cout << endl;  
21.        }  
22.       /*所以对于上面循环的代码，肯定是else分支执行，改动一下即可*/  
23. }  

/***************************************************************************************************************************************************/

//最终结果

[cpp]  view plain  copy

1. void permutation(int * arr,int m,int n){  
2.     if (m > n-1){  
3.         for (int j = 0;j < n;j++)  
4.             cout << arr[j]<<" ";  
5.         cout << endl;  
6.       }  
7. else{  
8.     for (int i = k;i < n;i++){  
9.         swap(arr[m],arr[i]);  
10.         permutation(arr,m+1,n);  
11.         swap(arr[m],arr[i]);  
12.         }  
13.     }  
14. }  

对于过程递归来说，在函数的设计过程中只要觉得这个位置所需要实现的功能就是这个函数的功能，就可以理所当然的递归调用自己。不要考虑任何的细节，满足条件即可。

二，结构上具有递归性

递归还有一种设计思路是按照本身结构上具有递归性，用上面的思路解释不通。例如逆向打印，链表逆转，二叉树遍历等，很多带有逆向操作的都可以递归，为什么呢？因为递归是按层执行，每一层函数调用产生的变量，结果等都会压入函数栈中，知道遇到出口，才依次弹栈，所以我们利用其弹栈的特性，在逐渐弹的过程中，去执行我们需要的代码，就可以实现逆向效果。

案例1：用递归逆向打印一个数组

逆向打印数组其实简单的不要不要的了，但是考虑过用递归去打印吗？逆向打印我们在过程上完全感觉不到存在什么递归性，但是由于这种线性结构，使得其具有递归结构性，所以也是可以逆向打印的。

递归逆向打印的设计思路就是让递归一直下去，知道达到最后的位置，然后设定为出口条件，此时就会依次弹出，在弹出的位置依次打印每一层的值。

和过程递归相同的是同样要时刻明确自己函数的功能。

[cpp]  view plain  copy

1. void reprint(int * arr,int i,int n)//用一个i来描述当前的位置，便于递归退出，如果没有i，就无法退出  
2. {  
3.     /*出口条件*/  
4.     if (i > n-1)  
5.         return;  
6.     /*这里在不停的递归，知道当i == n的时候就开始弹他会弹到上一层调用的地方，并且开始执行调用函数下面的语句*/  
7.     reprint(i+1)  
8.     /*弹出后就会到这个位置来开始执行下面的语句，所以我们只需要在这里打印即可*/  
9.     cout << arr[i];  
10. }  

案例2：单向链表逆转

单向链表的逆转也是用递归来实现了，有了上面的案例一，是否会有些启发呢。单向链表只能从后面开始逆转，从前面开始逆转的话，由于没有前指针，所以会断掉，只能从后开始逆转。所以可以考虑用递归先将节点位置定位到最后，然后利用其弹栈的过程实现逆转。

1. void reverse(ListNode * node){  
2.     /*到最后的时候node肯定为空，就相当于遇到了出口*/
3.     if (node && node->next){  
4.         reverse(node->next);  
5.         /*这个位置就相当于处理递归回弹过程中next指针的指向*/
6.         node->next->next = node;  
7.     }  
8. }  

案例3：二叉树中序遍历

1. //中序遍历以参数root为根的子树  
2. static void travel(BSTREE_NODE * root){  
3.     if (root){  
4. /*这个过程有两个位置有递归*/
5.         travel(root->left);  
6.         printf("%d ",root->data);  
7.         travel(root->right);  
8.     }  
9. }  

二叉树的前序遍历和后序遍历同理。理解二叉树各序遍历组好找个二叉树图，然后结合代码来理解。