TAK Function

The TAK function is a recursive function devised by I. Takeuchi in 1978 (Knuth 1998). For integers , , and , it is defined by

(1)

This can be described more simply by

(2)

Let count the executions of the "otherwise" branch when the recursive definition is fully expanded, without reusing previously computed values. Then

(3)

The total number of function calls is (Knuth 1991).

An auxiliary recurrence relation, related to the ballot problem, omits the last recursive call:

(4)

For integers , it satisfies

			(5)
			(6)

(Knuth 1991).

The Takeuchi numbers are defined by for integers .