[資料結構(Data Structure, DS)] 基礎遞迴
費伯那西數
- 用遞迴設計費伯那西數(Fibonacci Number,費氏數)演算法
- 費伯那西數
n 0 1 2 3 4 5 6 7 8 9 10 Fn 0 1 1 2 3 5 8 13 21 34 55 - F0 = 0, F1 = 1
- F2 = F0 + F1 = 1
- F3 = F1 + F2 = 2
- Fn = Fn-2 + Fn-1
- 設計遞迴
- Base Case：
- if n = 0 return 0
- if n = 1 return 1
- General Case：if n > 1 return Fn-1 + Fn-2
- Base Case：
- 遞迴演算法
int Fibonacci(int n) { if( n <= 1) return (n); else return Fibonacci(n-1) + Finonacci(n-2); }int Fibonacci(int n) { if( n <= 1) return (n); else return Fibonacci(n-1) + Finonacci(n-2); }int Fibonacci(int n) { if( n <= 1) return (n); else return Fibonacci(n-1) + Finonacci(n-2); }int Fibonacci(int n) { if( n <= 1) return (n); else return Fibonacci(n-1) + Finonacci(n-2); } - 迴圈演算法
int Fibonacci(int n) { if( n <= 1 ) return n; int fa = 0, fb = 1, fn; for(int i = 0; i <= n; i++){ fn = fa + fb; fa = fb; fb = fn; } return fi; }int Fibonacci(int n) { if( n <= 1 ) return n; int fa = 0, fb = 1, fn; for(int i = 0; i <= n; i++){ fn = fa + fb; fa = fb; fb = fn; } return fi; }int Fibonacci(int n) { if( n <= 1 ) return n; int fa = 0, fb = 1, fn; for(int i = 0; i <= n; i++){ fn = fa + fb; fa = fb; fb = fn; } return fi; }int Fibonacci(int n) { if( n <= 1 ) return n; int fa = 0, fb = 1, fn; for(int i = 0; i <= n; i++){ fn = fa + fb; fa = fb; fb = fn; } return fi; } - 問題：若執行Fibonacci(4)，會呼叫Fibonacci( )幾次?
- ∴共9次
- 費伯那西數