Ackermann function illustrated

README.md

The below is an ackermann function implementation in awk based on the one on rosettacode.org and modified for higher verbosity to illustrate the details of calculations behind the ackermann function's recursion.

For example, the following shows Ackermann(2,2)

> awk -v m=2 -v n=2 -f ackermann_illustrated.awk


a(2,2) = a(1, a(2,1))
  a(2,1) = a(1, a(2,0))
    a(2,0) = a(1,1)
      a(1,1) = a(0, a(1,0))
        a(1,0) = a(0,1)
          a(0,1) = 2
        a(1,0) = 2
      a(1,1) = a(0, 2)
        a(0,2) = 3
      a(1,1) = 3
    a(2,0) = 3
  a(2,1) = a(1, 3)
    a(1,3) = a(0, a(1,2))
      a(1,2) = a(0, a(1,1))
        a(1,1) = a(0, a(1,0))
          a(1,0) = a(0,1)
            a(0,1) = 2
          a(1,0) = 2
        a(1,1) = a(0, 2)
          a(0,2) = 3
        a(1,1) = 3
      a(1,2) = a(0, 3)
        a(0,3) = 4
      a(1,2) = 4
    a(1,3) = a(0, 4)
      a(0,4) = 5
    a(1,3) = 5
  a(2,1) = 5
a(2,2) = a(1, 5)
  a(1,5) = a(0, a(1,4))
    a(1,4) = a(0, a(1,3))
      a(1,3) = a(0, a(1,2))
        a(1,2) = a(0, a(1,1))
          a(1,1) = a(0, a(1,0))
            a(1,0) = a(0,1)
              a(0,1) = 2
            a(1,0) = 2
          a(1,1) = a(0, 2)
            a(0,2) = 3
          a(1,1) = 3
        a(1,2) = a(0, 3)
          a(0,3) = 4
        a(1,2) = 4
      a(1,3) = a(0, 4)
        a(0,4) = 5
      a(1,3) = 5
    a(1,4) = a(0, 5)
      a(0,5) = 6
    a(1,4) = 6
  a(1,5) = a(0, 6)
    a(0,6) = 7
  a(1,5) = 7
a(2,2) = 7

ackermann_illustrated.awk

# Usage:
#         To illustrate Ackermann(2,2):
#         awk -v m=2 -v n=2 -f ackermann_illustrated.awk
#
#         To illustrate Ackermann(2,3):
#         awk -v m=2 -v n=3 -f ackermann_illustrated.awk

function myprint(s, n) {
  # Print string prefixed with n spaces (to illustrate stack depth in verbosity)
  i = 0
  while (i++ < n) printf "  "
  printf(s)
  printf("\n")
}


function ackermann(m, n, d)
{
  if ( m == 0 ) {
    x = n + 1
    myprint("a(" m "," n ") = " x, d)
    return x
  }
  if ( n == 0 ) {
    myprint("a(" m "," n ") = a(" m-1 "," 1 ")", d)
    x = ackermann(m-1, 1, d+1)
    myprint("a(" m "," n ") = " x, d)
    return x
  }
  myprint("a(" m "," n ") = a(" m-1 ", a(" m "," n-1 "))", d)
  y = ackermann(m, n-1, d+1)

  myprint("a(" m "," n ") = a(" m-1 ", " y ")", d)
  x = ackermann(m-1, y, d+1)
  myprint("a(" m "," n ") = " x, d)
  return x
}

BEGIN {
  ackermann(m,n)
}