玩转算法与数据结构之递归算法—HIT2000鲁天伟递归算法在数据结构的树，图程序中都有应用。

那么什么是递归算法呢。

其实就是函数的自我调用。

循环的在作一件事，把一个问题分成了可以重复的子问题去处理。

递归这个词有两层含义，即递去和归来。

递去，就是函数一层一层的在调用自己，我们在这里定义调用自己的函数为父函数，被调用的是子函数。

父与子是个相对概念（参照二叉树中父结点与子结点来理解）。

递去，何时结束呢，是要设定一个结束条件。

那么这种结束条件的设置，第一种是设全局变量，全局变量随着每次自我调用在变化，当全局变量达到指定值或是全局变量参与的计算达到某个指定的值时结束。

第二种是形参变量在被调用时达到指定值或形参参与的计算达到某个值时结束。

第三种是当不满足自我调用条件时结束。

这三种结束条件结合程序的需要可以组合使用。

归来是指调用到某一次时，子程序执行结束了，子函数一层一层的把程序的执行权返还给自己的父函数，父函数执行所调用子函数的下一条命令。

简单的递归，是一个函数体中调用自己一次，复杂的是在函数体中调用自己多次。

举一个字符串逆序输出的简单递归调用的例子如下图。

图表 1 递归函数调用1、字符串逆序输出问题：将一个长为4的字符串逆序输出。

代码如下：#include<stdio.h>#define MAXSIZE 4char data[MAXSIZE];Rverse(int n){if(n<MAXSIZE){Rverse(n+1);printf("%c",data[n]);}}void main(){printf("Input %d letters”,MAXSIZE);gets(data);Rverse(0);getch();}上面这段代码完成了，长度为4的任意字符串的逆序输出。

由于打印的语句在递归函数自我调用之后，所以打印是在归来时开始的，从后向前打印。

那如果把上面代码中标红的两句代码上下换个位置，那么就是正序打印了，也就是在递归函数自我调用之前打印，在递去的过程中打印。

递去过程中正序打印，归来过程中是逆序打印。

正序打印递归调用如下：Rverse(int n){if(n<MAXSIZE){printf("%c",data[n]);Rverse(n+1);}}修改成如下while循环代码Rverse(int n){while(n<MAXSIZE){printf("%c",data[n]);n=n+1;}}上述两段代码执行效果相同。

2、斐波那契级数问题求解F(n)=F(n-1)+F(n-2); n>=3,F(1)=1,F(2)=1 代码如下：#include<stdio.h>int Fib(int N){if(N<=1)return N;elsereturn Fib(N-1)+Fib(N-2);}int n;int result;do{printf("Input n ,if you want to quit please input -1\n"); scanf("%d",&n);if(n==-1)break;result=Fib(n);printf("Fib(%d) is %d\n",n,result);}while(1);getch();}3、阶乘问题：N！=N*(N-1)! 1!=1 代码如下：#include<stdio.h>int NJ(int n){if(n==1)return1;else{return n*NJ(n-1);}}void main(){int n;int result;do{printf("Input n you want to caculate n!,Input -1 to quit\n"); scanf("%d",&n);if(n==-1)break;result=NJ(n);printf("%d! is %d\n",n,result);}while(1);getch();}4、乘法运算：M*N=M*（N-1）N=1时返回M 代码如下：#include<stdio.h>int Multiply(int M,int N){if(N==1)return M;elsereturn M+Multiply(M,N-1);}int M,N;int a;int result;do{printf("Pleaese input the data you want to Multiply format:M N.Ifquit input -1 -1\n");scanf("%d %d",&M,&N);result=Multiply(M,N);if(M==-1)break;printf("%d * %d is %d\n",M,N,result);}while(1);getch();}5、组合的计算，从m个物品中选出n个物品有几种选法C n m=C n m-1+C n-1 m-1m>=n n>=0 #include<stdio.h>int zuhe(int m,int n){if(m==n || n==0)return1;elsereturn zuhe(m-1,n)+zuhe(m-1,n-1);}void main(){int m,n;int result;do{printf("Please input format:m n ;（m>=n) if you want to quit input -1 -1 \n");scanf("%d %d",&m,&n);if(m==-1)break;else if(m<n){continue;}else{result=zuhe(m,n);printf("C %d %d is %d\n",m,n,result);}}while(1);getch();}6、求两个数的最大公因数。

#include<stdio.h>int GCD(int M,int N){if(N==0)return M;elsereturn GCD(N,M%N);}void main(){int m,n;int result;do{printf("Please input M N format:M N,(M>=N)if you want to quit input -1 -1\n");scanf("%d %d",&m,&n);if(m==-1)break;if(m<n)continue;else{result=GCD(m,n);printf("Zui da gong yin zi is %d\n",result);}}while(1);getch();}7、汉诺塔问题，把n个圆盘，从A柱通过B柱全部移到C柱，圆盘在A柱上从上到下越来越大。

在移动的过程中，大圆盘不能放在小圆盘上。

图表 2 汉诺塔示意图#include<stdio.h>int count=0;void hanoi(int n,char a,char b,char c){if(n!=0){hanoi(n-1,a,c,b);count++;printf("step %d:Move %d %c->%c\n",count,n,a,c);hanoi(n-1,b,a,c);}}void main(){int n;do{count=0;printf("Please input n,if you want to quit,please input -1\n"); scanf("%d",&n);if(n==-1)break;elsehanoi(n,'A','B','C');}while(1);getch();}上述代码运行一下，对于n个圆盘的搬运，搬运的总次数是2n-1次。

8、迷宫问题，从指定的入口进，从指定的出口出。

代码实现如下：#include<stdio.h>int chess[7][7]={0,1,1,1,1,1,1,1,0,1,1,0,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0,0,1,};int migong(int x,int y){if(x==6&& y==5){chess[x][y]=2;return1;}if(x<0|| x>6|| y<0|| y>6)else{if(chess[x][y]==0)/*0表示可以走*/chess[x][y]=2;/*用2标记已走过，避免走回头路*/elsereturn0;if(migong(x-1,y))return1;if(migong(x-1,y+1))return1;if(migong(x,y+1))return1;if(migong(x+1,y+1))return1;if(migong(x+1,y))return1;if(migong(x+1,y-1))return1;if(migong(x,y-1))return1;if(migong(x-1,y-1))return1;chess[x][y]=3;/*标3以后不再考虑这个位置，这个位置8面都不通*/return0;}}void main(){int i,j;migong(0,0);for(i=0;i<7;i++){for(j=0;j<7;j++){printf("%d ",chess[i][j]);}printf("\n");}getch();}9、N皇后问题，在一个N*N的棋盘上，放置N个皇后，使以每个皇后的为中心的八个方向上都没有其它皇后存在。

程序实现如下：#include<stdio.h>#define MAX 10char chess[MAX][MAX];/*===判断x行，y列这个位置是否能放皇后===*/int Place(int x,int y){int i,j;if(chess[x][y]=='Q') return0;j=y-1;while(j>=0){if(chess[x][j--]=='Q') return0;}j=y+1;while(j<MAX){if(chess[x][j++]=='Q') return0;}i=x-1;while(i>=0){if(chess[i--][y]=='Q') return0;}i=x+1;while(i<MAX){if(chess[i++][y]=='Q') return0;}i=x-1;j=y-1;while(i>=0&& j>=0){if(chess[i--][j--]=='Q') return0;}i=x+1;j=y-1;while(i<MAX && j>=0){if(chess[i++][j--]=='Q') return0;}i=x+1;j=y+1;while(i<MAX && j<MAX){if(chess[i++][j++]=='Q') return0;}i=x-1;j=y+1;while(i>=0&& j<MAX){if(chess[i--][j++]=='Q')return0;}return1;}int Queen(int x,int y,int N){int i,j;int result=0;chess[x][y]='Q';if(N==MAX)return1;else{for(i=0;i<MAX;i++){for(j=0;j<MAX;j++){if(Place(i,j)){result=Queen(i,j,N+1);if(result==1)return1;}}}chess[x][y]='X'; /*尝试了所有点，都无法再放一个皇后，这个位置不能放Q*/ return0;}}void main(){int i,j,x,y;do{for(i=0;i<MAX;i++){for(j=0;j<MAX;j++){chess[i][j]='X';}}printf("Input x,y you put Queen first.If you want to quit,please input -1 -1\n");scanf("%d %d",&x,&y);if(x==-1)break;else{Queen(x,y,1);for(i=0;i<MAX;i++){for(j=0;j<MAX;j++){printf("%c ",chess[i][j]);}printf("\n");}}}while(1);getch();}我自己使用的环境是运用notepad++编辑，在notepad++里调用Dev-CPP里的编译和运行。