淺談遞歸思想（圖碼齊解）

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; (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;}