An implementation of the Ackermann function in Python.

ackermann.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import time


class Ackermann:
    def __init__(self):
        self.count = 0
        self.cache = {}
        self.cache_hit = 0
        self.cache_miss = 0

    def a0(self, x, y):
        """ Ackermann's function with naive recursion. """

        self.count += 1

        if x == 0:
            return y + 1
        elif y == 0:
            return self.a0(x - 1, 1)
        else:
            return self.a0(x - 1, self.a0(x, y - 1))

    def a1(self, x, y):
        """ Ackermann's function with Memoization """

        self.count += 1

        if x in self.cache and y in self.cache[x]:
            self.cache_hit += 1
            return self.cache[x][y]
        else:
            self.cache_miss += 1

            if x == 0:
                result = y + 1
            elif y == 0:
                result = self.a1(x - 1, y)
            else:
                result = self.a1(x - 1, self.a1(x, y - 1))

            self.cache[x] = {y: result}

        return result

    def a2(self, x, y):
        """ Ackermann's function with partial recursion """

        self.count += 1

        if x == 0:
            return y + 1
        elif x == 1:
            return y + 2
        elif y == 0:
            return self.a2(x - 1, 1)
        else:
            return self.a2(x - 1, self.a2(x, y - 1))

    def a3(self, x, y):
        """ Ackermann's function with Memoization + partial recursion """

        self.count += 1

        if x in self.cache and y in self.cache[x]:
            self.cache_hit += 1
            return self.cache[x][y]
        else:
            self.cache_miss += 1

            if x == 0:
                result = y + 1
            if x == 1:
                result = y + 2
            elif y == 0:
                result = self.a3(x - 1, 1)
            else:
                result = self.a3(x - 1, self.a3(x, y - 1))

            self.cache[x] = {y: result}

        return result

    def run(self, x, y):
        return self.a3(x, y)


if __name__ == '__main__':
    x = int(input('Please enter the first parameter: '))
    y = int(input('Please enter the second parameter: '))

    sys.setrecursionlimit(5000)

    ackermann = Ackermann()
    time1 = time.perf_counter()
    print(f'Ackermann ({x}, {y}): {ackermann.run(x, y)}')
    time2 = time.perf_counter()

    time_diff = time2 - time1
    print(f'Execution time: {time_diff}')
    print(f'Number of calls: {ackermann.count}')

    if ackermann.cache != {}:
        print(f'Cache hit count: {ackermann.cache_hit}')
        print(f'Cache miss count: {ackermann.cache_miss}')

    print(f'Cache Hit ratio: {ackermann.cache_hit / ackermann.cache_miss * 100}.2f')