浅谈递归思想（图码齐解）

2019-11-08 19:50:29

字体：大中小

来源：转载

供稿：网友

一、浅谈定义

1.官方定义：把一个直接调用自己或者通过一系列调用语句间接调用自己的函数称，递归函数 2.个人归纳定义：其实函数递归就是函数不断套用自己，直到到达判定条件，然后像入栈出栈那样，出栈进行下一步条件，如果真难理解，可以不要把一个递归函数中调用自己的函数看作调用自己，而就当它是在调另一个函数，只不过和自己长的一模一样

二、图码齐解

1、斐波那契（兔子的生殖）

兔子个数函数图 分别是n=0，n=1，n>1

(1).迭代法

//打印前40位int main(){ int i; int a[40]； a[0]=0; a[1]=1; PRintf("%d ",a[0]); printf("%d ",a[1]); for(i=2;i<40;i++) { a[i]=a[i-1]+a[i-2]; printf("%d ",a[i]); } return 0;}

(2).递归法

//40位int Fbi(int i){ if(i<2) return i==0?0:1; return Fbi(i-1)+Fbi(i-2);//递归了}int main(){ int i; for(i=0;i<40;i++) printf("%d ",Fbi(i)); return 0;}

斐波那契数列递归图解

2、汉诺塔递归思想

1.将one上的（除了最后一个盘子）其他都借助three移动到two 2.将one那个最后一个盘子移动到three 3.将two上的所有盘子借助one，移动到three 目的是将one所有盘子移动到three，且小盘一定要在大盘上

（1）.码解

//编辑器 vim/************************************************************************* > File Name: 汉诺塔.c > Author: geeker > Mail: 932834897@QQ.com > Created Time: 2017年02月15日星期三 12时29分39秒 ************************************************************************/#include<stdio.h>void move(int m,char one,char two,char three){ if(1==m) printf("%c-->%c/n/n",one,three); else { move(m-1,one,three,two);//这个move递归了再出栈进行下面 printf("%c-->%c/n/n",one,three); move(m-1,two,one,three); }}int main(){ int n; printf("请输入你要几个盘子/n"); scanf("%d",&n); printf("%d个盘子的移动步骤是：/n",n); move(n,'A','B','C'); return 0;}

（2）.图解

汉诺塔按箭头为步骤

3、八皇后问题

（8*8的棋盘，8个皇后不能出现在同列，同行，同斜方向）

（1）.码解

/************************************************************************* > File Name: 八皇后.c > Author: geeker > Mail: 932834897@qq.com > Created Time: 2017年02月15日星期三 12时35分56秒 ************************************************************************/#include<stdio.h>int count=0;int notdanger(int row,int list,int (*disc)[8]){ int i,j,flag1=0,flag2=0,flag3=0,flag4=0,flag5=0; //判断列方向,就是需要这一列上没有棋子 for(i=0;i<8;i++) { if(*(*(disc+i)+list)!=0)//说明这一列，有棋子了，就是已经存在了，要换，退出循环 { flag1=1; break; } } //判断左上方 for(i=row,j=list;i>=0&&j>=0;i--,j--) { if(*(*(disc+i)+j)!=0) { flag2=1; break; } } //判断右下方 for(i=row,j=list;i<8&&j<8;i++,j++) { if(*(*(disc+i)+j)!=0) { flag3=1; break; } } //判断右上方 for(i=row,j=list;i>=0&&j<8;i--,j++) { if(*(*(disc+i)+j)!=0) { flag4=1; break; } } //判断左下方 for(i=row,j=list;i<8&&j>=0;i++,j--) { if(*(*(disc+i)+j)!=0) { flag5=1; break; } } if(flag1||flag2||flag3||flag4||flag5)//只要有一个flag是1，那么就算失败返回0 { return 0; } else { return 1; }}//row：表示起始行，注意row不是表示行数，而是起始行//list：表示列数void EightQueen(int row,int list,int (*disc)[8])//最后一个的定义方式可以谷歌.意思为参数（*disc）[8]表示指向棋盘每一行的指针{ int disc2[8][8],i,j;//*(*(disc2+x)+i)表示x是代表第几行，i代表第几列 for(i=0;i<8;i++) { for(j=0;j<8;j++) { disc2[i][j]=disc[i][j]; } } if(8==row) { printf("第%d种可能/n",count+1); for(i=0;i<8;i++) { for(j=0;j<8;j++) { printf("%d ",*(*(disc2+i)+j)); } printf("/n"); } printf("/n"); count++; } else//1.判断这个位置是否有危险2.如果没有危险，继续往下 { for(j=0;j<list;j++) { if(notdanger(row,j,disc)) { for (i=0;i<8;i++)//没有危险，先将这一行的每一列都赋值为0，0代表没有皇后，1代表有皇后 { *(*(disc2+row)+i)=0; } *(*(disc2+row)+j)=1; EightQueen(row+1,list,disc2); } } }}int main(){ int disc[8][8],i,j; for(i=0;i<8;i++) { for(j=0;j<8;j++) { disc[i][j]=0; } } EightQueen(0,8,disc); printf("总共有%d种方法/n/n",count); return 0;}