Problem Statement

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:

Its arguments are never negative and it always terminates.

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.

Let's start with the solution:

MODULE ackerman;

IMPORT  Out;

VAR     m, n    : INTEGER;

PROCEDURE Ackerman (x, y   : INTEGER) : INTEGER;

BEGIN
  IF    x = 0  THEN  RETURN  y + 1
  ELSIF y = 0  THEN  RETURN  Ackerman (x - 1 , 1)
  ELSE
    RETURN  Ackerman (x - 1 , Ackerman (x , y - 1))
  END
END Ackerman;

BEGIN
  FOR  m := 0  TO  3  DO
    FOR  n := 0  TO  6  DO
      Out.Int (Ackerman (m, n), 10);
      Out.Char (9X)
    END;
    Out.Ln
  END;
  Out.Ln
END ackerman.