首页 > 代码库 > 递归讨论（三）
递归讨论（三）
递归对于编程者来说，是比较难理解的，但当你完全清晰程序思路时，它会变得容易理解了。
递归思想成为解决一些编程难题所常用的，所以多多练习，多多理解它，会让我们对之爱不释手，作为初学者的我，每当理解如何递归的解决问题时，就会非常开心，这也许就是挑战所带来的成就感，所学即所得的满足感吧。
下面以如下一道例题为例吧：
在数据结构（c语言版）一书中，页码p8，有如下一题
问题1：<全排列>对给定的n个元素的集合，输出该集合所有可能的排列；
我们对比着看下面一道问题，可以先思考思考：
问题2：<全排列>对给定的n个元素的序列（可能含重复元素），输出该序列所有可能的排列。（后面来解析该题。）
我们来先说说问题1吧：
即然是n个元素的集合，那么由众所周知的集合定义，我们可以明确得出：这n个元素是互不相同的。
那么问题转换为求n个不重复元素的全排列，同问题2有着显著区别哦。
对于该问题：
首先对于全排列：
首字符是这n个元素中的其中一个，如果首字符不同，我们得到的排列也必是不同的。
其次：（核心思想）
我们可以先预定某个元素为首字符，再对剩余字符进行全排列（嘿嘿，此处是不是回归到我们开始要求的问题了呀，只不过此处变成了对n-1的全排列了啊，这这。。。显然明确是递归的结构啊）
最后：
我们循环的将首字符换成与之前不同的字符（这句话要好好理解，问题2的小核心），再对剩余进行全排列，直至首字符遍历完n个元素。
文字太枯燥，来个例子，比如：对{a,b,c,d}进行全排列，
以a为头，对{b,c,d}进行全排列
以b为头，对{a,c,d}进行全排列
以c为头，对{a,b,d}进行全排列
以d为头，对{a,b,c}进行全排列
问题的规模，在递归的结构下，由规模4变成了规模3了，然后规模3又在递归的结构下变成了规模2.。。。。。最后递归到只有1个规模了，那么此时，说明当前递归已到递归基上了，说明已进行了一次全排列。此时我们就可以输出当前的排列了。
运行到此处，我们还要注意些程序实现的细节，不然很难实现最终的结果哦。
先上个代码，代码里有相关说明，会让你更明白些。
#include<iostream>void perm(char*,int,int);
int main(){ using namespace std; char* p=new char[4]; for(int i=0;i<4;i++) cin >> *(p+i); perm(p,0,3); cout << num; for(int i=0;i<4;i++) cout << p[i] << "--"; delete[] p; return 0;} //递归产生的全排列void perm(char* p,int a,int b) //a表示待全排的数组下标开始，b表示下标尾{ if(a == b) //递归基，说明只有一个元素了 { for(int i=0;i<=b;i++) //此时按下标顺序输出当前数组中的元素，因为数组通过交换元素的方式实现了排列。 { std::cout << p[i]; } std::cout << std::endl; } else { for(int j=a;j<=b;j++) //该处的循环作用就是，让首字符取遍所有可能字符，每次循环，都会将首字符为当前循环 //字符的所有可能排列全部输出 { std::swap(p[a],p[j]); //此处就是通过交换元素的方式让当前首字符更改，不同于之前循环，也惟有这样处理，、 //首字符才可能取遍所有可能字符 perm(p,a+1,b); //此处递归调用，因为首字符我们已经确定了，我们只需对剩余元素进行全排列，所以只需作a+1处理即可 std::swap(p[a],p[j]); //将数组还原到初始状态，对于此处，开始我比较难理解，下面画个调用图，看看它是如何还原的 } }}
为了简化时序分析，我们这里分析的是3个元素的全排序，其调用如下图所示：
我们可以在这里清晰的看到调用的过程，以及相关变量的值变化。我们如果由3个元素推广更多的元素，我们会发现其中很多自相似的调用图谱。另外我们也注意到，在一个完整的for循环中，每个循环开始前，p数组的序列都是一样的。
主要由于两个swap的作用，也算是此处的小核心了。
也惟有保证每次循环前，p序列回归原始状态，我们才能保证下次循环开始，将下一个不同的字符放在首字符。
下面这个图画的略草，但还可以凑和着看了。
我们总结问题1的解决方案：
首先要保证首字符能取遍所有可能字符，再对余下字符进行全排列
其次在排列完后，我们要把字符序列回复到原始状态，
这个过程类似走路一样，我们怎么走去的，我们原路返回，我们就能准确的回归到原点。（这个有点意思呵，仔细想想就是哦）。
下面我们来分析分析问题2：
首先说下排列数，对于aabbbccdd，它的排列数算法如下：
(具体算法自己查书去,或者自己回高中学学排列组合)
问题2与1的主要区别在于，2中的序列可能含重复的，所以算法过程会有所区别，但两者的算法思想在大致都差不多，
但问题2多了的是判断，要判断的是我们是否产生了重复排列。
若按照问题1的思路，我们确定首字符，然后排列剩余的，
因为存在相同字符，我们可能会把某个字符两次或多次放在首字符，但这种情况，两者要排序的内容完全，
首字符都一样，剩余的字符肯定也是完全一样的啊，那么排列的内容就重复了啊。
所以我们要在此处添加一个判断，我们遍历时，将当前字符与其之前的字符（即已经遍历过的字符）相比较，若在遍历过的字符中发现了同样的字符，那么我们就立即结束当前循环，进入下次循环。呵呵，这样就跳过重复了。也是比较好理解的了。
代码如下：
#include<iostream>void perm(char*,int,int);int main(){ using namespace std; bool flag=true; while(flag) { cout << "input the number:"; int n; cin >> n; cout << "enter " << n << " character:"; char* p=new char[n]; for(int i=0;i<n;i++) cin >> *(p+i); perm(p,0,n-1); cout << "continue?(y/n)"; char ch; cin >> ch; if(ch!=‘y‘) { flag=false; } delete[] p; } return 0;}void perm(char* p,int a,int b){ if(a == b) { for(int i=0;i<=b;i++) { std::cout << p[i]; } std::cout << std::endl; } else { for(int j=a;j<=b;j++) { bool flag = false; for(int i=a;i<j;i++) { if(p[i]==p[j]) { flag = true; } } if(flag) { continue; } std::swap(p[a],p[j]); perm(p,a+1,b); std::swap(p[a],p[j]); } }}
运行结果如下：
由于这个全排列成阶乘特征，比较大，下面的程序就只显示排列数了：
#include<iostream>void perm(char*,int,int,int&);int main(){ using namespace std; bool flag=true; while(flag) { int num=0; cout << "input the number:"; int n; cin >> n; cout << "enter " << n << " character:"; char* p=new char[n]; for(int i=0;i<n;i++) cin >> *(p+i); perm(p,0,n-1,num); cout << "the number of permutation:" << num << endl; cout << "continue?(y/n)"; char ch; cin >> ch; if(ch!=‘y‘) { flag=false; } delete[] p; } return 0;}void perm(char* p,int a,int b,int& num){ if(a == b) { num++; } else { for(int j=a;j<=b;j++) { bool flag = false; for(int i=a;i<j;i++) { if(p[i]==p[j]) { flag = true; } } if(flag) { continue; } std::swap(p[a],p[j]); perm(p,a+1,b,num); std::swap(p[a],p[j]); } }}
运行结果如下：
递归讨论（三）