递归是一个非常重要的解题方法和思路，我们在生活中很多地方都用到了递归概念。现有一字符串序列，要求我们对其进行全排列，例如“ab”的全排列为“ab”和”ba”，编写程序解决问题。
在数学中全排列问题是一个非常常见的问题，在概率问题中经常出现，通常全排列都是用大写字母A来表示。我们在数学中确实经常做到全排列的题，但是，我们很少让写出全排列，大部分问题都是让我们求出对于一个序列，全排列的个数，有可能确实有让写全排列的，但是其阶数最大基本上不超过3，因为阶数为4时，全排列的个数已经是十位数了，所以我们很少体验到写高阶全排列的过程，而做的基本上都是算排列的个数。现在我们举个例子：求出序列abcd的全排列个数。非常简单，答案是24，方法是4*3*2*1 = 24。但是，这个求解个数的方法，其实也是使用了递归思想，现在让我们捋一捋这里面的关系：“4”代表什么?”4″代表第一位可以出现的字符的个数，当我们考虑第一位时，所有的四个字符都还没有动用，因此他们四个均可以出现在第一位；那么”3″又是什么呢?它的意思是当第一位确定后，第二位可能出现的字符的个数；同理，“2”是前两位确定后，第三位可能出现的字符的个数；最后，“1”是前三位确定后，最后一位出现的字符个数。这些数字相乘，就代表了全排列出现的所有可能。
注意，这个结果出现的前提是字符中没有重复元素
，如果有的话就要另当别论了。
这里体现的递归思想只要思考一下就可体会出来，首先我们在考虑第一位时，有四种可能，此时我们考虑的是长度为4的序列的开头元素，而当第一为元素确定以后，我们去考虑第二位的元素，理所当然只有三个，这是因为第一位已经占用了一个，这是理所当然的。确实这种理解方式不算错，但是我们也可以通过另一个角度去看，我们确定第一位后，便不再考虑第一位，将第二位当作一个长度为三的序列的首位，我们从三个元素中去挑一个来作为它的首位；而第三位使用同样的思路去考虑，就是在一个长度为2的序列中，从两个元素中去挑一个作为它的首位。它的递归思想就这样出来了。
简单来说，就是：阶数为四的全排列，我们可以化解成两个基本问题，一个问题是从四个之中选出一个作为它的首位；另一个问题是，选出来的这个元素后面只要接上一个三阶的全排列，那么这个元素为首的所有排列就得出来了。因此我们只要不断变换开头元素，然后去求去掉这个元素的全排列，即可得到所有的全排列。解决这个问题的方法买就是递归，下面我用图解来详细说明。首先是基本思路的概述：
然后是我们得到其中一种排列的过程：
这样，问题就基本上明了了，递归过程其实就是忽略开头元素，去求解一个比自己当前阶数少一阶的序列的全排列，而这个子问题的全排列的解决也是一个同样的过程，这样就完全符合递归思想了。我们只要在每一个进程中，让当前规模下序列的每一个元素做一遍开头，然后进入递归调用即可解决问题。下面是代码：
#include <stdio.h>
#define G 100
void permute(int start,int end,char list[]); //排列函数，start为开始位置下标，end为结束为止下标
void move(int a,int b,char list[]);//位置交换函数，用于让每个元素做开头，改变元素在数组中的位置
int main(void){
char my_list[G];
int i = 0;
printf("请输入字符元素:");
while((my_list[i]=getchar())!='\n')i++;
my_list[i] = '\0';
printf("排列情况:\n");
permute(0,i-1,my_list);
}
void permute(int start,int end,char list[]){
int i;
if(start == end){//当开始位置下标和结束位置下标相等时，意味着当前的数组中只有一个元素了
printf("%s\n",list);//此时应该输出
return;
}else{//否则的话就要进行递归调用
for(i = start;i<=end;i++){//i用于便利当前规模的问题，让每个元素当开头
move(start,i,list);//移动位置，做出移动操作
permute(start+1,end,list);//进行递归调用，将开头加一，代表不去考虑第一个元素，进一步去考虑剩下三个元素。其实就是去解决剩下三个元素的全排列
move(start,i,list);//问题解决完之后，再移动回来
}
}
}
void move(int a,int b,char list[]){
char temp;
temp = list[a];
list[a] = list[b];
list[b] = temp;
return;
}输入及运行结果：
其他测试可自行实验。
以上问题解决的是序列元素中没有重复元素时的情况，当序列元素中有重复情况时，需要进行一些修改，下面附上修改后的代码，这个代码可以解决当序列中有重复元素时的全排列问题。
#include <stdio.h>
#define G 100
void permute(int start,int end,char list[]); //排列函数，start为开始位置下标，end为结束为止下标
void move(int a,int b,char list[]);//位置交换函数，用于让每个元素做开头，改变元素在数组中的位置
int find_no_same(char list[],int pre,int start); //用于查看是否有和自己一样的
int main(void){
char my_list[G];
int i = 0;
printf("请输入字符元素:");
while((my_list[i]=getchar())!='\n')i++;
my_list[i] = '\0';
printf("排列情况:\n");
permute(0,i-1,my_list);
}
void permute(int start,int end,char list[]){
int i;
if(start == end){//当开始位置下标和结束位置下标相等时，意味着当前的数组中只有一个元素了
printf("%s\n",list);//此时应该输出
return;
}else{//否则的话就要进行递归调用
for(i = start;i<=end;i++){//i用于便利当前规模的问题，让每个元素当开头
if(find_no_same(list,i,start)){
move(start,i,list);//移动位置，做出移动操作
permute(start+1,end,list);//进行递归调用，将开头加一，代表不去考虑第一个元素，进一步去考虑剩下三个元素。其实就是去解决剩下三个元素的全排列
move(start,i,list);//问题解决完之后，再移动回来
}
}
}
}
void move(int a,int b,char list[]){
char temp;
temp = list[a];
list[a] = list[b];
list[b] = temp;
return;
}
int find_no_same(char list[],int pre,int start){
int i = start;
for(;i<pre;i++){
if(list[pre]==list[i]){
return 0;
}
}
return 1;
} 具体原理比较简单，大家参考代码既可以明白，下面是测试样例与输出：
