[資料結構(Data Structure, DS) 教學 教程 教材 Tutorial] 基礎遞迴 - 艾克曼函數
YehYeh\'s Notepad yehyeh@gmail.com 

[資料結構(Data Structure, DS)] 基礎遞迴

艾克曼函數

  • 用遞迴設計艾克曼函數(Ackermann's Function)演算法
    • 艾克曼函數(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)
      • ∴Ackermann(2, 2)=7,共呼叫Ackermann( )29次