Функция Аккермана без рекурсии

В той же Википедии есть ссылка на реализацию без рекурсии.

https://doi.org/10.1016%2F0304-3975%2888%2990046-1

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

def ack1(i, n):
    stack = []
    stack.append(i)
    stack.append(n)
    while len(stack) > 1:
        n_cur = stack.pop()
        i_cur = stack.pop()
        if i_cur == 0:
            stack.append(n_cur + 1)
        elif n_cur == 0:
            stack.append(i_cur - 1)
            stack.append(1)
        else:
            stack.append(i_cur - 1)
            stack.append(i_cur)
            stack.append(n_cur - 1)
    result = stack.pop()
    return result

for i in range(4):
    for j in range(4):
        a1 = ack(i, j)
        a2 = ack1(i, j)
        print(a1, a2)
        assert a1 == a2

ВДОГОНКУ

вот здесь приведена реализация, которая напрямую вычисляет функцию Аккермана A(i,n), без итераций и рекурсий. Реализация теоретически неверная, но даёт правильные ответы во всех случаях, когда значение функции Аккермана имеет разумные размеры. Если же значение не вмещается в нашу Вселенную, эта релизация выбрасывает исключение, не дожидаясь конца времён.

ИСХОДНЫЙ ОТВЕТ

Из того же источника, что и ответ @maestro, второй вариант: без стека, цикл длиной m*ack(m,n) на двух массивах размерами (m+1) и (n+1)

Функция ack_2 уделывает по производительности стековые реализации. Например, легко и непринуждённо считает A(4,1), которую не смогла посчитать рекурсивная функция (переполнение стека), а функцию из ответа @maestro с внутренним стеком я не дождался.

В теории, эта реализация может посчитать функцию Аккермана для любых аргументов, в отличие от рекурсивной реализации и реализации с внутренним стеком. Но только в теории. На практике даже для вычисления A(4,2) потребуется порядка 10^20_000 (десять в степени ДВАДЦАТЬ ТЫСЯЧ) операций. Столько не живут. Даже наша вселенная - по оценкам, последняя чёрная дыра испарится через 10^107 лет, после чего в пустой вселенной не останется барионной материи, и считать будет не на чем.

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

    
def ack_2(i, n):
    """
    Вычисляет функцию Аккермана без рекурсии.
    Подробности см. в статье Jerrold W. Grossman and R.Suzanne Zeitman
    "An inherently iterative computation of ackermann's function"
    https://doi.org/10.1016%2F0304-3975%2888%2990046-1
    
    Аргументы:
        i (int): Степень гипероперации, i >= 0.
        n (int): Аргумент гипероперации, n >= 0.
    Возвращаемое значение:
        int: значение функции Аккермана.
    """
    vals = [0] * (i + 1)
    goal = [1] * (i) + [-1]
    
    while True:
        value = vals[0] + 1
        for j, v in enumerate(vals):
            vals[j] += 1
            if v == goal[j]:
                goal[j] = value
            else:
                break

        if vals[i] == n + 1:
            return value


    
for i in range(4):
    for n in range(4):
        a1 = ack(i, n)
        a2 = ack_2(i, n)
        print((i,n), a1, a2)
        assert a1 == a2

(0, 0) 1 1
(0, 1) 2 2
(0, 2) 3 3
(0, 3) 4 4
(1, 0) 2 2
(1, 1) 3 3
(1, 2) 4 4
(1, 3) 5 5
(2, 0) 3 3
(2, 1) 5 5
(2, 2) 7 7
(2, 3) 9 9
(3, 0) 5 5
(3, 1) 13 13
(3, 2) 29 29
(3, 3) 61 61

'''
Написать скрипт, вычисляющий функцию Аккермана без применения рекурсии
'''

import os
import time

def ackermann(m, n):
    stack = [(m, n)]
    while stack:
        m, n = stack.pop()
        if m == 0:
            n += 1
            if stack:
                stack[-1] = (stack[-1][0], n)
        elif n == 0:
            stack.append((m - 1, 1))
        else:
            stack.append((m - 1, None))
            stack.append((m, n - 1))
    return n

m, n = 2, 0  # Пример значений для функции Аккермана
start_time = time.time()
result = ackermann(m, n)
execution_time = time.time() - start_time

print(f"Результат функции Аккермана A({m}, {n}) = {result}")
print(f"Время выполнения: {execution_time:.6f} секунд")

print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")

Результат:

Результат функции Аккермана A(2, 0) = 3
Время выполнения: 0.000006 секунд

Ответы @maestro и мой теоретически верные - имея в распоряжении бесконечную память и бесконечное время, обе реализации смогут вычислить функцию Аккермана для любых аргументов, но на практике...

Уже A(4,3) равно 2**(2**65536) - 3 - это число непредставимо, даже если взять все компьютеры мира. Да что там компьютеры - даже если мы возьмём всю барионную материю вселенной, нам не хватит атомов для хранения битов этого числа.

Поэтому нужно трезво смотреть на вещи и не пытаться вычислять функцию Аккермана для тех аргументов, которые приведут к заведомо непредставимым результатам. А при таких вводных функция Аккермана вычисляется явно, без итераций и тем паче рекурсии.

Как определить, при каких значениях аргументов функция Аккермана практически не вычислима? Для этого воспользуемся тем фактом, что функция Аккермана A(i,n) выражается через гипероператор h_i(a, b):

A(i, n) = h_i(2, n + 3) - 3

Поэтому достаточно определить, когда гипероператор уходит в практическую бесконечность.

Гипероператор задаётся рекурсивно в том же стиле, что и функция Аккермана:

h_0(a, b) = 1 + b
h_1(a, b) = a + b
h_2(a, b) = a*b

При i > 2:
h_i(a, 0) = 1
h_i(a, b) = h_{i-1}(a, h_i(a, b-1))

Теперь следите за руками

В общем случае гипероператор вычисляется итеративно, но фокус в том, что для i=0,1,2,3 есть явные формулы вычиления h_i(a,b), а для порядков i > 3 практически вычислимых значений h_i(2,b) всего ничего:

h_i(2, 0) = 1 для всех i > 3
h_i(2, 1) = 2 для всех i > 3
h_i(2, 2) = 4 для всех i > 3

h_4(2, 3) = 16
h_4(2, 4) = 65536
h_4(2, 5) = 2**65536

h_5(2, 3) = 65536

Всё! для всех остальных значений n при i > 3 значения непредставимы.

Введём функцию вычисления гипероператора для основания 2: hyper_2(i,n) == h_{i}(2,n)

Зная скорость роста гипероператора для i и n, эту функцию можно задать так:

# Все представимые значения гипероператора 4-го порядка для основания 2
hyper_2_4_values = {
    0: 1,
    1: 1 << 1,
    2: 1<< (1 << 1),
    3: 1 << (1 << (1 << 1)),
    4: 1 << (1 << (1 << (1 << 1))),
    5: 1 << (1 << (1 << (1 << (1 << 1)))),
}

# Все представимые значения гипероператора 5-го порядка для основания 2
hyper_2_5_values = {
    0: 1,
    1: 2,
    2: 4,
    3: 65536,
}

# Все представимые значения гипероператора порядка выше 2-го для основания 2
hyper_2_any_values = {
    0: 1,
    1: 2,
    2: 4,
}

# Табличное задание гипероператора порядка n для основания 2
hyper_2_n_values = {
    4: hyper_2_4_values,
    5: hyper_2_5_values,
}

def hyper_2(n: int, exponent: int) -> int:
    """
    Вычисляет гипероператор порядка n с основанием 2 с заданным показателем.

    Параметры:
    n (int): Порядок гипероператора. Должен быть неотрицательным целым числом.
    exponent (int): Показатель гипероператора. Должен быть неотрицательным целым числом.

    Возвращает:
    int: Результат гипероператора порядка n для основания 2 с заданным показателем.

    Исключения:
    ValueError: Если значение слишком велико для вычисления, выбрасывается исключение.
    """
    if n < 0 or exponent < 0:
        raise ValueError("Порядок и показатель гипероператора должны быть неотрицательными числами")
    if n == 0:
        return 1 + exponent
    if n == 1:
        return 2 + exponent
    if n == 2:
        return 2 * exponent
    if n == 3:
        return 2 ** exponent

    if n in hyper_2_n_values and exponent in hyper_2_n_values[n]:
        return hyper_2_n_values[n][exponent]
    elif exponent in hyper_2_any_values:
        return hyper_2_any_values[exponent]

    raise ValueError(
        f"Гипероператор порядка {n} числа 2"
        f" с показателем {exponent} слишком велик для вычисления"
    )

Итого получается: самая быстрая прямая реализация функции Аккермана, без СМС и переплат рекурсии и итераций :)

def ack_hyper(i:int, n:int) -> int:
    """
    Вычисляет функцию Аккермана через гипероператор.

    Параметры:
    i (int): Первый аргумент функции Аккермана, порядок гипероператора. 
             Должен быть неотрицательным целым числом.
    n (int): Второй аргумент функции Аккермана, показатель гипероператора равен n+3.
             Должен быть неотрицательным целым числом.

    Возвращает:
    int: Значение функции Аккермана.
    
    Исключения:
    ValueError: Если значение слишком велико для вычисления.
    """
    return hyper_2(i, n+3) - 3

Пример:

import sys
import math

for i in range(10):
    for n in range(10):
        try:
            val = ack_hyper(i, n)
        except ValueError as e:
            print(f"A({i}, {n}) не получилось: {e}")
            break
        # по-умолчанию в Python не печатают числа длиннее, 
        # чем 4300 цифр, то есть более, чем ~14300 бит
        if (val.bit_length() > sys.get_int_max_str_digits() * math.log2(10)):
            print(f"A({i}, {n}): превышает лимит числа цифр: {val.bit_length()} бит")
        else:
            print(f"A({i}, {n}) = {val(i, n)}")

Вывод:

A(0, 0) = 1
A(0, 1) = 2
A(0, 2) = 3
A(0, 3) = 4
A(0, 4) = 5
A(0, 5) = 6
A(0, 6) = 7
A(0, 7) = 8
A(0, 8) = 9
A(0, 9) = 10
A(1, 0) = 2
A(1, 1) = 3
A(1, 2) = 4
A(1, 3) = 5
A(1, 4) = 6
A(1, 5) = 7
A(1, 6) = 8
A(1, 7) = 9
A(1, 8) = 10
A(1, 9) = 11
A(2, 0) = 3
A(2, 1) = 5
A(2, 2) = 7
A(2, 3) = 9
A(2, 4) = 11
A(2, 5) = 13
A(2, 6) = 15
A(2, 7) = 17
A(2, 8) = 19
A(2, 9) = 21
A(3, 0) = 5
A(3, 1) = 13
A(3, 2) = 29
A(3, 3) = 61
A(3, 4) = 125
A(3, 5) = 253
A(3, 6) = 509
A(3, 7) = 1021
A(3, 8) = 2045
A(3, 9) = 4093
A(4, 0) = 13
A(4, 1) = 65533
A(4, 2): превышает лимит числа цифр: 65536 бит
A(4, 3) не получилось: Гипероператор порядка 4 числа 2 с показателем 6 слишком велик для вычисления
A(5, 0) = 65533
A(5, 1) не получилось: Гипероператор порядка 5 числа 2 с показателем 4 слишком велик для вычисления
A(6, 0) не получилось: Гипероператор порядка 6 числа 2 с показателем 3 слишком велик для вычисления
A(7, 0) не получилось: Гипероператор порядка 7 числа 2 с показателем 3 слишком велик для вычисления
A(8, 0) не получилось: Гипероператор порядка 8 числа 2 с показателем 3 слишком велик для вычисления
A(9, 0) не получилось: Гипероператор порядка 9 числа 2 с показателем 3 слишком велик для вычисления