Recursion Benchmark

"""
The Ackermann function, due to its extremely deep recursion, can be
used as a benchmark of a 'compiler's' ability to optimize recursion.
see: http://en.wikipedia.org/wiki/Ackermann_function
"""

import sys
sys.setrecursionlimit(10**9)

def ack(m, n):
    # count recursions
    global recursion_count
    recursion_count += 1
    if recursion_count % 10000000 == 0:
        print( "now %s recursions" % recursion_count )
    if m == 0:
        return n+1
    elif n == 0:
        return ack(m-1, 1)
    else:
        return ack(m-1, ack(m, n-1))

recursion_count = 1
print('start (use a stop watch to time each 10,000,000 recursions)')

# don't wait for the result if you are impatient
print( ack(4, 1) )