The Ackermann function is a classic example of a recursive function, notable especially because it is not a primitive recursive function. It grows very quickly in value, as does the size of its call tree.



The Ackermann function is usually defined as follows:







A
(
m
,
n
)
=


{



n
+
1



if 

m
=
0




A
(
m
−
1
,
1
)



if 

m
>
0

 and 

n
=
0




A
(
m
−
1
,
A
(
m
,
n
−
1
)
)



if 

m
>
0

 and 

n
>
0.








{\displaystyle A(m,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A(m-1,A(m,n-1))&{\mbox{if }}m>0{\mbox{ and }}n>0.\end{cases}}}






Its arguments are never negative and it always terminates.



Task

Write a function which returns the value of 



A
(
m
,
n
)


{\displaystyle A(m,n)}

. Arbitrary precision is preferred (since the function grows so quickly), but not required.



See also

 Conway chained arrow notation for the Ackermann function.


' version 28-10-2016
' compile with: fbc -s console
' to do A(4, 2) the stack size needs to be increased
' compile with: fbc -s console -t 2000
 
Function ackerman (m As Long, n As Long) As Long
 
    If m = 0 Then ackerman = n +1
 
    If m > 0 Then
        If n = 0 Then
            ackerman = ackerman(m -1, 1)
        Else
            If n > 0 Then
                ackerman = ackerman(m -1, ackerman(m, n -1))
            End If
        End If
    End If
End Function
 
' ------=< MAIN >=------
 
Dim As Long m, n
Print
 
For m = 0 To 4
    Print Using "###"; m;
    For n = 0 To 10
        ' A(4, 1) or higher will run out of stack memory (default 1M)
        ' change n = 1 to n = 2 to calculate A(4, 2), increase stack!
        If m = 4 And n = 1 Then Exit For 
        Print Using "######"; ackerman(m, n);
    Next
    Print
Next
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End