鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第五章：遞迴 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/

遞迴函數（Recursive Function） 遞迴函數的特徵： 直接或間接地呼叫自己 在數學上與遞迴定義有關 例如：費氏數列

求算階乘（Factorial） n! = n*(n-1)*(n-2)*…*2*1 遞迴定義： 1!=1 f(n)=n*f(n-1), n>=2 13! = 1932053504，在32位元系統上用long所能算出的最大階乘數 long fact(int n) { if (n == 1) return 1; else return n * fact(n-1); }

費氏數列（Fibonacci Series） 問題：給定一個 n 值，求解費氏數列第 n 項的值。

費氏數列（Fibonacci Series） int fibon(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibon(n-1) + fibon(n-2); } 時間複雜度：O(2n/2)

二元搜尋（Binary Search） 輸入： 輸出： n 筆已排序資料（從小排到大） 欲尋找之資料 target 1 2 3 4 5 6 7 8 9 找 5 大 小 中

二元搜尋（Binary Search） int bin_search(int data[], int left, int right, int target) { int mid = (left + right) / 2; if (left > right) return -1; if (target == data[mid]) return mid; if (target > data[mid]) { return bin_search(data, mid+1, right, target); } else { return bin_search(data, left, mid-1, target); } 用法： bin_search(data, 0, n-1, target)

Tower of Hanoi

Tower of Hanoi

Tower of Hanoi 宣告與用法 #define PEG_A "PEG_A" #define PEG_B "PEG_B" #define PEG_C "PEG_C" int main(int argc, char* argv[]) { … hanoi_move(n, PEG_A, PEG_B, PEG_C); }

Tower of Hanoi 主要邏輯 void hanoi_move(int n, char* from, char* to, char* via) { if (n == 1) { printf("Move ring 1 from %s to %s\n", from, to); } else { hanoi_move(n-1, from, via, to); printf("Move ring %d from %s to %s\n", n, from, to); hanoi_move(n-1, via, to, from); }

Tower of Hanoi 執行結果 1: Move ring 1 from PEG_A to PEG_B 2: Move ring 2 from PEG_A to PEG_C 3: Move ring 1 from PEG_B to PEG_C 4: Move ring 3 from PEG_A to PEG_B 5: Move ring 1 from PEG_C to PEG_A 6: Move ring 2 from PEG_C to PEG_B 7: Move ring 1 from PEG_A to PEG_B

八個皇后 西洋棋盤上，皇后不可以在同一列（row）或同一行（column）或同一對角線（diagonal）上 在一個 8×8 的棋盤上如何放置 8 個皇后？ 往回追蹤（Backtracking）又稱『回溯』 如果下一個皇后找不到位置可放，則回頭調整前一個皇后的位置

void place(int q) { int i; i = 0; while (i < MAXQUEEN) { /* 試著將第 q 個皇后放在 (row, col) = (i, q) 的位置 */ if (!attack(i, q)) { /*皇后未受攻擊 */ queen[q] = i; /*儲存皇后所在的列位置 */ /*判斷是否找到一組解 */ if (q == (MAXQUEEN - 1)) output_solution(); /*列出此組解 */ else place(q + 1); /*否則繼續擺下一個皇后 */ } i++;

/* 測試在(row,col)上的皇后是否遭受先前放置的其他皇后攻擊 */ int attack(int row, int col) { int i, atk = FALSE; int offset_row, offset_col; i = 0; while (!atk && i < col) { offset_col = ABS(i - col); offset_row = ABS(queen[i] - row); /*判斷兩皇后是否在同一列,皇后是否在對角線上 */ /*若皇后同列或在對角線上則產生攻擊,atk ==TRUE */ atk = (queen[i] == row) || (offset_row == offset_col); i++; } return atk;

計算組合數 組合數 在 m 個球之中取 n 個，有多少種方式？ 遞迴解：

計算組合數 int comb(int m, int n) { if (n == 0) return 1; if (m == n) return 1; return comb(m-1, n) + comb(m-1, n-1); }