[資料結構(Data Structure, DS)] 基礎遞迴
艾克曼函數
- 用遞迴設計艾克曼函數(Ackermann's Function)演算法
- 艾克曼函數(Ackermann's Function):
- 艾克曼函數是一種輸出值增長很快的遞迴函式
-
m/n 0 1 2 3 4 n 0 1 2 3 4 5 n+1 1 2 3 4 5 6 n+2 2 3 5 7 9 11 2×(n+3)-3 3 5 13 29 61 125 2(n+3)-3
- 設計遞迴
- Base Case:if m==0 return n+1
- General Case:
- if m>0 & n==0 return Ackerman(m-1, 1)
- Otherwise return Ackerman(m-1, Ackerman(m, n-1))
- 遞迴演算法
int Ackermann(int m, int n) { if (m == 0) return n + 1; else if (m > 0 && n == 0) return Ackermann(m - 1, 1); else return Ackermann(m - 1, Ackermann(m, n - 1)); }
int Ackermann(int m, int n) { if (m == 0) return n + 1; else if (m > 0 && n == 0) return Ackermann(m - 1, 1); else return Ackermann(m - 1, Ackermann(m, n - 1)); }
int Ackermann(int m, int n) { if (m == 0) return n + 1; else if (m > 0 && n == 0) return Ackermann(m - 1, 1); else return Ackermann(m - 1, Ackermann(m, n - 1)); }
int Ackermann(int m, int n) { if (m == 0) return n + 1; else if (m > 0 && n == 0) return Ackermann(m - 1, 1); else return Ackermann(m - 1, Ackermann(m, n - 1)); }
- 問題:若執行Ackermann(2, 2),要呼叫Ackermann( )幾次?
- ∴Ackermann(2, 2)=7,共呼叫Ackermann( )29次
- 艾克曼函數(Ackermann's Function):