Module grscheller.boring_math.recursive

Recursive function module.

• function ackermann_list: eval Ackermann's function simulating recursion with a list

Functions

def ackermann_list(m: int, n: int) ‑> int

Ackermann function is defined recursively by

   ackermann(0,n) = n+1
   ackermann(m,0) = ackermann(m-1,1)
   ackermann(m,n) = ackermann(m-1, ackermann(m, n-1)) for n,m > 0

Ackermann's function is an example of a function that is computable but not primitively recursive. It quickly becomes computationally intractable for relatively small values of m.