递归函数的两个应用类型：

一、用递归写递推

1、找到第n次与第n-1次之间的关系

2、确定第1次（或者是第1、2次）的返回结果

eg.

求Fabonacci数列 

int f( int n ){
if(n==1||n==2){   //确定第1次（或者是第1、2次）的返回结果
return 1;
}else if(n==0){
return 0;
}else{
return f(n-1)+f(n-2);  //第n次与第n-1次之间的关系
}
}

二、模拟连续发生的动作

eg.

汉诺（Hanoi）塔问题

#include <stdio.h>

void hanoi(int n,char a,char b,char c);
int main()
{
int n;
scanf("%d",&n);
hanoi(n,'a','c','b');

return 0;
}
void hanoi(int n,char a,char b,char c){
if(n==1)
printf("%c-->%c\n",a,c);
else{
hanoi(n-1,a,c,b);
printf("%c-->%c\n",a,c);
hanoi(n-1,b,a,c);

}
}

1、连续发生的动作

void hanoi(int n,char a,char b,char c);

把盘子通过b从a移到c

2、不同动作之间的关系

hanoi(n-1,a,c,b);
printf("%c-->%c\n",a,c);
hanoi(n-1,b,a,c);

多个盘子时，将其看为两个部分，第一个部分除最底下的所有盘子，第二部分最下面盘子；

hanoi(n-1,a,c,b); 将第一部分从a到b

printf("%c-->%c\n",a,c); 将最底下盘子从a到c

hanoi(n-1,b,a,c); 将第一部分从b到c

3、边界条件

if(n==1)
printf("%c-->%c\n",a,c);

一个盘子的时候从a到c

递归实现输出全排列：

请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。

输入格式:

输入给出正整数n（<10）。

输出格式:

输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序，即序列a1​,a2​,⋯,an​排在序列b1​,b2​,⋯,bn​之前，如果存在k使得a1​=b1​,⋯,ak​=bk​ 并且 ak+1​<bk+1​。

输入样例：

3

输出样例：

123
132
213
231
312
321

首先用一个数组存储1到N。每次把1个数字挑出来放到最左边，然后递归地排列剩下的数字；
当只剩下1个数字时，就进行输出。
输出后再把那个挑出来的数字换回原位，继续挑下一个数字放到最左边，依次将数组内的所有数字均挑一遍。

#include <stdio.h>

void p(int a[],int m,int n);  //m为最左边的数组元素下标，n为最右边
int main()
{
int n;
int a[10];
scanf("%d",&n);
for(int i=0;i<n;i++){  //用一个数组存储1到N

a[i]=i+1;
}
p(a,0,n-1);

return 0;
}
void p(int a[],int m,int n){
if(m==n){
for(int i=0;i<=n;i++){
printf("%d",a[i]);
}
printf("\n");
}else{
for(int i=m;i<=n;i++){
int x=a[m];  //把要交换的数字交换到最左边
a[m]=a[i];
a[i]=x;
p(a,m+1,n);
int t=a[i];  //交换回来
a[i]=a[m];
a[m]=x;
}

}
}

但运行结果并不是按字典序输出，eg. 以四位数为例，当3放到最左边时，剩下的数排列为214，则先输出3214，而按照字典序应先输出3124.

为了保证字典序输出，每当挑出1个数字放到最左边时，需要将该数字的左边所有数字整体右移。将挑出的数字放回原位时，将所有右移的数字整体左移，恢复原状。

#include <stdio.h>

void p(int a[],int m,int n);  //m为最左边的数组元素下标，n为最右边
int main()
{
int n;
int a[10];
scanf("%d",&n);
for(int i=0;i<n;i++){  //用一个数组存储1到N

a[i]=i+1;
}
p(a,0,n-1);

return 0;
}
void p(int a[],int m,int n){
if(m==n){
for(int i=0;i<=n;i++){
printf("%d",a[i]);
}
printf("\n");
}else{
for(int i=m;i<=n;i++){
int x=a[i];
for(int k=i;k>m;k--){  //整体右移
a[k]=a[k-1];
}
a[m]=x;
p(a,m+1,n);
for(int k=m;k<i;k++){  //整体左移，恢复原状
a[k]=a[k+1];
}
a[i]=x;
}
}
}