' http://largeint.sourceforge.net/Ackerman.htm

uses console

int c,s,d
sub init_counts()
   c=0 : s=0 : d=1
end sub

' Naive implementation with three recursive calls:
function A (int m, n) as int
   c = c + 1
   s = s + 1
   if s > d then d = s

   if m = 0 then
      function = n + 1
   elseif n = 0 then
      function = A(m - 1, 1)
   else
      function = A(m - 1, A(m, n - 1))
   end if
   s = s - 1
end function

init_counts() : printl "Ackermann function A(m,n) - three recursive calls"
init_counts() : printl "A(3, 7) = " : print A(3,7)  tab " calls: " c " depth: " d '1021
init_counts() : printl "A(3,12) = " : print A(3,12) tab " calls: " c " depth: " d '32765; A(3,13) -> stack overflow
init_counts() : printl "A(4, 0) = " : print A(4,0)  tab " calls: " c " depth: " d '13; A(4,1) -> stack overflow


' Cheat - direct computation for m < 4
function A (int m, n) as quad
   c++
   s++
   if s > d then d = s
      select case m
      case 0
         function = n + 1
      case 1
         function = n + 2
      case 2
         function = 2 * n + 3
      case 3
         function = 2 ^ (n + 3) - 3
      case else
         if n = 0 then
            function = A(m - 1, 1)
         else
            function = A(m - 1, A(m, n - 1))
         end if
      end select
   s--
end function

printl
init_counts() : printl "Ackermann function A(m,n) - direct computation for m < 4 "
init_counts() : printl "A(3, 7) = " : print A(3,7)  tab " calls: " c " depth: " d '1021
init_counts() : printl "A(3,12) = " : print A(3,12) tab " calls: " c " depth: " d '32765; A(3,13) -> stack overflow
init_counts() : printl "A(4, 0) = " : print A(4,0)  tab " calls: " c " depth: " d '13; A(4,1) -> stack overflow
printl
init_counts() : printl "A(3,20) = " : print A(3,20) tab " calls: " c " depth: " d '8388605
init_counts() : printl "A(3,30) = " : print A(3,30) tab " calls: " c " depth: " d '858934589
init_counts() : printl "A(4, 1) = " : print A(4, 1) tab tab " calls: " c " depth: " d '65533; A(4,2) too much -> 19729 digits
init_counts() : printl "A(5, 0) = " : print A(4, 1) tab tab " calls: " c " depth: " d '65533; A(5,1) wrong result


printl "Enter ..."
waitkey