Chap7 Recursive.

Presentation on theme: "Chap7 Recursive."— Presentation transcript:

1 Chap7 Recursive

2 Recursive 遞迴Recursive 自己呼叫自己(但參數不一樣) 有一使遞迴終止的條件
將大問題分割成較小的問題, 分別解決後, 然後再把結果整合起來

3 遞迴式的函式

4 遞迴式的函式

5 遞迴式的函式

6 遞迴式的函式

7 遞迴式的函式

8 遞迴式的函式

9 遞迴式的函式 程式未完, 接下頁

10 遞迴式的函式 接上頁

11 遞迴式的函式

12 N 階乘(N!) long Factorial(long n) { if ( n == 1 || n== 0) return (1);
else return( n * Factorial(n-1)); }

13 Fibonacci number Fibonacci number費氏數列 其中某一項為前二項之和,且第0項為0,第1項為1
費氏數列為0,1,1,2,3,5,8,12,21,…

14 Fibonacci number long Fibonacci(long n) { if ( n == 0) /*第0項為 0 */
return (0); else if ( n == 1 ) /*第1項為 1 */ return (1); else /*遞迴呼叫函數 第N項為n-1 跟 n-2項之和*/ return( Fibonacci(n-1) + Fibonacci(n-2) ); }

15 河內塔 河內塔問題目的乃在三根柱子中,將n個盤子從A 柱子搬到 C 柱中,每次只移動一盤子,而且必須遵守每個盤子都比其上面的盤子還要大的原則。 河內塔問題的想法必須針對最底端的盤子。 我們必須先把A柱子頂端n-1個盤子想辦法(借助C柱)移至B柱子, 然後才能將想最底端的盤子移至C柱。 此時C有最大的盤子,B總共n-1個盤子,A柱則無。 要再借助A柱子，將B柱n-1個盤子移往C柱即可 : HanoiTower(n-1,A,C,B); 將A頂端n-1個盤子借助C移至B HanoiTower(n-1,B,A,C); 將B上的n-1個盤子借助A移至C

16 遞迴問題範例—河內之塔

17 遞迴問題範例—河內之塔

18 遞迴問題範例—河內之塔 程式未完, 接下頁

19 遞迴問題範例—河內之塔 接上頁

20 遞迴問題範例—河內之塔