第 5 章 遞迴

目次 5.1 遞迴的運作方式 5.2 一個典型的遞迴範例：河內塔 5.3 另一個範例：八個皇后 5.4 何時不要使用遞迴

5.1 遞迴的運作方式 何謂遞迴(Recursive)？ Ex 1 ：n 階層 (某一數A的階層 = A * (A-1)階層) 5.1 遞迴的運作方式 何謂遞迴(Recursive)？ 一個呼叫它本身的函數 撰寫遞迴時，一定要有「結束點」 Ex 1 ：n 階層 (某一數A的階層 = A * (A-1)階層) n! = n * (n-1)! (n-1)! = (n-1) * (n-2)! (n-2)! = (n-2) * (n-3)! ： 　 1! = 1

5.1 遞迴的運作方式(con.t) 以遞迴方式計算 n! (結束點為 n = 1) int fact(int n) { int ans; if(n == 1) ans = 1; else ans = n * fact(n-1) return ans; }

5.1 遞迴的運作方式(con.t) 以圖形表示 n!的做法(以4!為例) num = fact(4); 24 6 2 1 n = 4; ans = 4 * fact(3); return(ans); n = 3; ans = 3 * fact(2); n = 2; ans = 2 * fact(1); n = 1; ans = 1; 6 2 1 24

5.1 遞迴的運作方式(con.t) Ex 2：費氏數列(Fibonacci number) n2 = n1+n0=1+1=2 某一數為其前二個數的和 假設 n0=1， n1=1，則 n2 = n1+n0=1+1=2 n3 = n2+n1=2+1=3 ： ∴ ni = ni-1+ni-2

5.1 遞迴的運作方式(con.t) 費氏數列函數 int fibon(int n) { int ans; if(n == 0 || n == 1) ans = 1; else ans = fibon(n-1)+fibon(n-2); return(ans); }

5.2 一個典型的遞迴範例：河內塔 河內塔遊戲規則： 每次只能搬一個盤子 盤子有大小之分，而且大盤子在下，小盤子在上 河內塔搬移的演算法 5.2 一個典型的遞迴範例：河內塔 河內塔遊戲規則： 每次只能搬一個盤子 盤子有大小之分，而且大盤子在下，小盤子在上 河內塔搬移的演算法 假使 n = 1，則 搬移第一個盤子從A至C 否則 搬移n–1個盤子從A至B 搬移第n個盤子從A至C 搬移n–1個盤子從B至C

5.2 一個典型的遞迴範例：河內塔(con.t) 河內塔片段程式 void tower(char from,char to,char aux,int n) { if ( n == 1 ) printf("Move disk 1 from %c to %c\n",from,to); else{ tower(from,aux,to,n-1); /* 將 from 標記中的n-1個金盤子，藉助 to 標記的柱子，搬到aux標記的柱子 */ printf("Move disk %d from %c to %c\n",n,from,to); tower(aux,to,from,n-1); /* 將n-1個盤子從aux，藉助from搬到to */ }

5.3 另一個範例：八個皇后 八個皇后遊戲規則 八個皇后牽涉到的觀念 5.3 另一個範例：八個皇后 八個皇后遊戲規則 皇后之間不可在同一列(row)、同一行 (column)，也不可以在同一個對角線(diagonal)上。 左上角為(第一列、第一行) 八個皇后牽涉到的觀念 遞迴 往回追蹤(Backtracking)

5.3 另一個範例：八個皇后(con.t) /* 測試在(row,col)上的皇后是否遭受攻擊，遭受攻擊傳回值為1，否則為0 */ 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;

5.4 何時不要使用遞迴 遞迴雖然可以使用少數幾行的敘述就可解決一複雜的問題，但有些問題會導致花更多的時間，因此在何時使用遞迴是很重要的。 5.4 何時不要使用遞迴 遞迴雖然可以使用少數幾行的敘述就可解決一複雜的問題，但有些問題會導致花更多的時間，因此在何時使用遞迴是很重要的。 遞迴樹(recursive tree) Ex：費氏數列 遞迴 非遞迴，即以反覆的(interaive)方式執行 遞迴 vs. 非遞迴(課本表 5.1)

5.4 何時不要使用遞迴(con.t) 費氏數列 – 非遞迴 int fibon(int n) { int ans, i; int backbone = 1, backtwo = 2; if (n == 0 || n == 1) ans = 1; else{ for(i = 2; i<=n;i++){ ans = backone + backtwo; backtwo = backone; backbone = ans; } return ans;

5.4 何時不要使用遞迴(con.t) Ex： n! 的遞迴 遞迴 非遞迴 int fact(int n) int fact(int n) 遞迴 非遞迴 int fact(int n) int fact(int n) { { int ans; int i, ans = 1; if (a==1) for (i=n; i≦; i--) ans = 1; ans *= i; else return ans; ans = n*fact(n-1); } return ans; }

5.4 何時不要使用遞迴(con.t) 建議使用遞迴的時機 遞迴樹類似一棵木(如費氏數列的圖)，但重覆動作很少時 Ex：八個皇后 建議使用非遞迴的時機 遞迴樹類似灌木，但重覆動作很多的 遞迴樹類似一條通道的 Ex：費氏數列、n!