資料結構與C++程式設計進階 遞迴(Recursion) 講師：林業峻 CSIE, NTU 6/ 17, 2010

大綱 基本遞迴觀念 進階遞迴應用 分治法 (Divide and Conquer) 作業 河內塔遊戲 (Hanoi Tower) 快速排序法 (Quick Sort) 作業

遞迴 什麼是遞迴（Recursion）？ 範例 思考: 在函式(function)之中會需要呼叫到自己函式的程式寫法 寫一個void print(int n)函式 列出整數1~n 思考: 要印n前先印n-1 要印n-1前先印n-2 … 要印2前先印1 #include <stdio.h> void print(int n) { if(n<=1) // 遞迴終止條件 printf("%d\n", n); return; } else print(n-1); // 遞迴部分（呼叫自己） int main() print(10); // 印出1~10 return 0;

實例與應用 遞迴的特性 使用遞迴設計程式的步驟 呼叫與被呼叫的函式具有一個固定的關係，以下列的total函 式為例（傳入n印出1加到n的總和）： 使用遞迴設計程式的步驟 (1) 了解問題是否適合用遞迴的特性來解題 (2) 決定遞迴結束條件 (3) 決定遞迴執行部份 int total(int n) { if (n <=1) // 遞迴終止條件 return 1; else return (n+total(n-1)); // 遞迴部分（呼叫下一層的函式） }

範例：total 呼叫 return 6 印出6 呼叫 return 3 呼叫 return 1 int main() { printf(“%d\n”, total(3)); return 0; } int total(int d) // d =3 { if (d <=1) // 遞迴終止條件 return 1; else return (d+ total(d-1) ); } 呼叫 return 6 印出6 int total(int d) // d =2 { if (d <=1) // 遞迴終止條件 return 1; else return (d+ total(d-1)) ; } 呼叫 return 3 int total(int d) // d =1 { if (d <=1) // 遞迴終止條件 return 1; else return (d+ total(d-1) ); } 呼叫 return 1

費伯那西數列 – 使用for迴圈 費伯那西數列（每個數字為前兩個數字的和）： 範例程式（迴圈寫法）：印出第N個費伯那西數字 0, 1, 1, 2, 3, 5, 8, 13, 21…… F(n) = F(n-1) + F(n-2) 範例程式（迴圈寫法）：印出第N個費伯那西數字 int Fib(int n) { int a1, a2=0, a3=1, i; if(n<=1) return 0; else if(n==2) return 1; for(i=3; i<=n; i++) { a1=a2; a2=a3; a3=a1+a2; } return a3;

費伯那西數列 – 遞迴 思考: 我們得到： [迴圈 / 遞迴]費伯那西數列的比較 要算F(n)前先算F(n-1)+F(n-2) int Fib(int n) { if(n==1) return 0; else if(n==2) return 1; else return Fib(n-1)+Fib(n-2); } 思考: 要算F(n)前先算F(n-1)+F(n-2) 要算F(n-1)前先算F(n-2)+F(n-3) … 要印F(3)前先算F(2)+F(1) 我們得到： Fib(1) = 0, Fib(2) = 1, Fib(3) = 1, Fib(4) = 2, Fib(5) = 3 … [迴圈 / 遞迴]費伯那西數列的比較 迴圈寫法 遞迴寫法 程式行數 較長 較短 執行效率 較快 較慢

練習 寫一個遞迴函式, 可印出n~1 寫一個遞迴函式, 將一個鏈結串列從尾印到頭

大綱 基本遞迴觀念 進階遞迴應用 分治法 (Divide and Conquer) 作業 河內塔遊戲 (Hanoi Tower) 快速排序法 (Quick Sort) 作業

河內塔(Hanoi Tower) 河內塔問題：在A、B、C三個塔上有數個圓盤， 請求出將圓盤從A塔全數搬移到C塔的順序，且大 的圓盤不可以疊到小圓盤上。 B C 3 2 1 A 1 2 3 A B C B C 3 2 1 A B C 3 2 1 A B C 3 2 1 A B C 3 2 A 1 B C 3 2 1 A B C 3 2 1 A

河內塔(Hanoi Tower) 題目：印出河內塔中，編號1~n的圓盤從A塔到C 塔的搬動過程。 目標： 步驟： 2 3 A B C

河內塔範例程式碼 範例程式碼 功能：印出河內塔中，編號1~n的圓盤從A塔到C塔的搬動過 程。 void hanoi (int n, char from, char mid, char to) { // 在搬動第n個圓盤時 if(n==0) return ; // 先將第n-1個圓盤搬到”中間塔” hanoi(n-1,from, to, mid); // 將自己搬到”目標塔” printf("圓盤%2d從 %c塔 -> %c塔\n",n,from,to); // 再將第n-1個圓盤從”中間塔”搬回來 hanoi(n-1,mid, from, to); }

練習 請利用河內塔程式碼，讓使用者輸入「圓盤總數n 」，計算各圓盤被搬動多少次(圓盤最多不超過 100個)？ (chap04_ex1.c)

大綱 基本遞迴觀念 進階遞迴應用 分治法 (Divide and Conquer) 作業 河內塔遊戲 (Hanoi Tower) 快速排序法 (Quick Sort) 作業

分治法（Divide and Conquer） 分而治之、各個擊破 是一種利用遞迴特性解題的技巧。將一個大問題，切割成許 多小問題；將這些小問題解決之後，原本的大問題也就解決 了。 實例: 排序 (分類再分類, 直到無法再分為止!) 小 中 大 中 小 大 小 中 大

快速排序法(Quick Sort) 快速排序法 步驟說明（由小排到大） 是一種運用”切割並各個擊破”的方式，將一群資料切割成 兩個部分做排序。 步驟說明（由小排到大） (1) 在一群資料中訂出一個基準值 (2) 比基準值大的集中在右邊、比基準值小的集中在左邊 (a) 在這群資料中由左至右，找一個比基準值大的資料 (b) 在這群資料中由右至左，找一個比基準值小的資料 (c) 交換(a)、(b)中的資料，但如果(a)、(b)的搜尋相遇就停止 (3) 最後將基準值放在兩者之間，得到兩群子資料A、B。 (4) 對每群子資料做一樣的操作。

快速排序法(Quick Sort) 要決 小 中 大 中 小 大 中 小 大 小 中 大 小 中 大 小 中 大 小 中 大 分組再分組 (先分小的那組) 直到不能分 結束 小 中 大 中 小 大 中 小 大 小 中 大 小 中 大 小 中 大 小 中 大

快速排序法(Quick Sort) 範例圖示

快速排序法圖例(由小排到大) 第一步： 訂出基準值 5 1 6 4 8 7 5 pivot a b 第二步： 3) 交換兩者 *)若a,b交錯則跳到第3步 5 1 4 6 6 4 8 7 5 pivot 交換 b a 第三步： 將資料分為兩群，基準值放在中間 5 4 1 4 5 6 8 7 5 pivot 交換 第四步： 將左右兩區資料個別再做”快速排序” 1 6 8 7 4 5

快速排序法程式碼 (chap04_ex2.c) void QuickSort(int *numbers, int low, int high) // Quick Sort 由小排到大 { int a, b, pivot; a = low+1; // a從左邊開始找 b = high; // b從右邊開始找 pivot = numbers[low]; // 基準值預設為第一個 while(1) while(numbers[a] < pivot) // a向右找，找到比基準值大的才停下來 a++; while(numbers[b] > pivot) // b向左找，找到比基準值小的才停下來 b--; if(a < b) swap(&numbers[a], &numbers[b]); else break; } numbers[low] = numbers[b]; // 把基準值擺到中間 numbers[b] = pivot; // 把數列切成兩半 if((b-1) > low) QuickSort(numbers, low, b-1); // 小的那一半繼續做QuickSort if((b+1) < high) QuickSort(numbers, b+1, high); // 大的那一半繼續做QuickSort

大綱 基本遞迴觀念 進階遞迴應用 分治法 (Divide and Conquer) 作業 河內塔遊戲 (Hanoi Tower) 快速排序法 (Quick Sort) 作業

河內塔遊戲 2.0 寫一個河內塔遊戲程式碼，讓使用者輸入「圓盤 總數」，列出所有搬動過程並顯示三塔之情況 範例: http://www.csie.ntu.edu.tw/~d95027/train/download/HanoiTower2.exe B C 3 2 1 A 1 2 3 A B C B C 3 2 1 A B C 3 2 1 A B C 3 2 1 A B C 3 2 A 1 B C 3 2 1 A B C 3 2 1 A

繳交 使用FTP上傳 請使用FileZilla上傳作業至指定FTP主機 繳交期限：2010. 6/24(四) 主機： 使用者名稱： 密碼： 連接埠： 將程式存到自己學號之資料夾 (請自行新增) 檔名: ca1871XX_hw2_##.c XX為學號, ##為版本編號 Ex: ca187100_hw2_01.c (ca187100號同學 作業2 第1版) 請使用FileZilla上傳作業至指定FTP主機 繳交期限：2010. 6/24(四) 公佈解答後,不再收作業