Translate a recursive program from ALGOL60 to your favorite language, get it running and submit the results.

Essay on Ackermann’s Function, a non-primitive recursive function.

The Ackermann Function A(n, m) is defined for integers n and m as:

A(m, n) = n + 1 if m = 0

A(m, n) = A(m-1, 1) if n = 0

A(m, n) = A(m-1, A(m, n-1)) otherwise

Following is a program in ALGOL 60 I used to compute it and the UNIVAC 1107 program run in 1964 which shows a stack overflow at A(3,5). Write a program to compute Ackermann’s function in your language of choice and run it on your laptop to see how far it gets before experiencing stack overflow. Submit your code and the results like my 1964 UNIVAC 1107 run. If C is your language of choice there are free ALGOL60 to C converters available on the Internet for your use.

Ackermann Function

real procedure A (m,n); value m, n; real m,n;

begin if m = 0 then go to ONE;

if n = 0 then go to TWO;

THREE: A := A(m-1, A(m, n-1) ); go to FOUR;

ONE: A := n + 1; go to FOUR;

TWO: A := A(m-1, 1.0);

FOUR: end;

Driver: begin real m, n;

for m = 0 step 1 until 4 do

for n = 0 step 1 until 10 do

write (entier (m), entier (n), A (m, n) );

end;

A hardcopy handout of an ALGOL 60 run to be handed out in class will accompany this email transmission.