The Ackermann function is a famous function that played a big role in computability theory as the first example of a total computable function that is not primitive recursive.

Since then the function has been a bit simplified but is still of good use. Due to its definition in terms of extremely deep recursion it can be used as a benchmark of a compiler's ability to optimize recursion. 

The goal of this kata is to code a function which will be given two inputs, m and n, and will return the Ackermann number A(m,n) defined by:

```
A(m,n) = n+1                          if m=0  
A(m,n) = A(m-1,1)                     if m>0 , n=0
A(m,n) = A(m-1,A(m,n-1))              if m,n > 0
```

m,n should be non-negative integers, the function should return null (Javascript), None (Python), or nil (Ruby) for other type, non-integer and negative numbers. In C, input is restricted to integer type.

Source: codewars | Difficulty: EASY
Tags: Mathematics

Complete search

Starter code: def Ackermann(m,n):
	

Solutions:
from numbers import Number

def Ackermann(m, n):
	if isinstance(n, Number) and isinstance(m, Number):
		if m >= 0 and n >= 0:
			return Ackermann_Aux(m, n)
	return None

def Ackermann_Aux(m, n):
	if m == 0:
		return n + 1
	if m > 0:
		if n == 0:
			return Ackermann_Aux(m - 1, 1)
		if n > 0:
			return Ackermann_Aux(m - 1, Ackermann_Aux(m, n - 1))


def Ackermann(m, n):
	if type(m) is not int or type(n) is not int:
		return None
	if m < 0 or n < 0:
		return None
	if m == 0:
		return n + 1
	elif n == 0:
		return Ackermann(m - 1, 1)
	else:
		return Ackermann(m - 1, Ackermann(m, n - 1))


def Ackermann(m, n):
	return n + 1 if m == 0 else Ackermann(m - 1, 1) if n == 0 else Ackermann(m - 1, Ackermann(m, n - 1))


def val(v):
	return isinstance(v, int) and v >= 0

def Ackermann(m, n):
	if not val(m) or not val(n):
		return None
	if m == 0:
		return n + 1
	elif m > 0 and n == 0:
		return Ackermann(m - 1, 1)
	return Ackermann(m - 1, Ackermann(m, n - 1))


def Ackermann(m, n):
	try:
		if m == 0 and n >= 0:
			return n + 1
		if m > 0 and n == 0:
			return Ackermann(m - 1, 1)
		if m > 0 and n > 0:
			return Ackermann(m - 1, Ackermann(m, n - 1))
	except:
		return None


def deepAck(m, n):
	return n + 1 if m == 0 else deepAck(m - 1, 1) if n == 0 else deepAck(m - 1, deepAck(m, n - 1))

def Ackermann(m, n):
	return None if not isinstance(m, int) or not isinstance(n, int) or m < 0 or (n < 0) else deepAck(m, n)


def Ackermann(m, n):
	if m:
		if n:
			return Ackermann(m - 1, Ackermann(m, n - 1))
		return Ackermann(m - 1, 1)
	return n + 1


def Ackermann(m, n):
	return (lambda m, n, s=lambda m, n, f: n + 1 if m == 0 and n >= 0 else f(m - 1, 1, f) if m > 0 and n == 0 else f(m - 1, f(m, n - 1, f), f) if m > 0 and n > 0 else None: s(m, n, s))(m, n)