遞歸漢諾塔

 1 #include<stdio.h>
 2  
 3 void Hanoi(int count,char a,char b,char c){
 4 　　if(count == 1){
 5 　　　　printf("FROM %c TO %c\n",a,c);
 6 　　}else
 7 　　{
 8 　　　　Hanoi(count-1,a,c,b);
 9 　　　　printf("FROM %c TO %c\n",a,c);
10 　　　　Hanoi(count-1,b,a,c);
11 　　}
12 }
13 int main(){
14 　　printf("please input the number of Hanoi:");
15 　　int n;
16 　　scanf("%d",&n);
17 　　Hanoi(n,'A','B','C');
18 　　return 0;
19 }

通常系統通常在一個函數運行期間調用另一個函數時，在運行被調用的函數之前，系統需要做3件事：(1)將所有的實參，返回地址等信息傳遞給被調用的函數保存。(2)為被調用的函數的局部變數分配存儲區。(3)將控制轉到被調用的函數的入口。從而在被調用的函數返回調用函數之前，系統通常也要做3件事：(1)保存被調函數的計算結果(2)釋放被調函數的數據區(3)依照被調函數保存的返回地址將控制返回到調用函數。當有多個函數嵌套調用，按照先調用的後返回的原則，上述函數之間的信息傳遞和控制的轉移必須必須通過棧來實現，即系統見整個程式運行期間的所需要的數據空間安排在一個棧中，每當調用一個函數就為它在棧頂分配一個存儲區，每當一個函數退出運行時，就釋放他的存儲區，則當前正在運行的函數的數據必須是在棧頂的。遞歸函數的執行過程相當於多個韓式的嵌套調用，只是調用函數和被調用的函數是同一個函數。為了保證遞歸函數的正確進行，系統設立了一個遞歸工作棧作為真個遞歸函數運行期間使用的數據存儲區，每一層遞歸所需的信息構成一個“工作記錄”。其中包括所有的上一層的返回地址，所有的局部變數和實在的參數。每當進入一層遞歸，就產生一個新的工作記錄壓入棧頂，每當退出一層遞歸，就從棧頂彈出一項工作記錄。

void Hanoi(int count,char a,char b,char c)

1  {

2     if(count == 1)

3        printf("FROM %c TO %c\n",a,c);

4     else{

5        Hanoi(count-1,a,c,b);

6        printf("FROM %c TO %c\n",a,c);

7        Hanoi(count-1,b,a,c);

8     }

9  }

 下表給出了遞歸的執行過程，返回地址是程式中的代碼的行號，主函數的地址為0；