Можно ли вычислить рекурсивную функцию ackermann(m,n) с аргументами m>=4 и n>=1 в python без превышения максимальной глубины рекурсии?

Question

Можно вычислить общую вычислимую рекурсивную функцию ackermann(m,n) с аргументами m>=4 а также n>=1 в питоне без превышения максимальной глубины рекурсии?

def ackermann(m,n):

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

ackermann(4,1)

Answer 1

Для этого уровня ответа используйте динамическое программирование: запомните функцию. Это означает, что вы ведете таблицу предыдущих результатов. Если вы найдете результат, который уже был вычислен, вы вернете его из таблицы. Только когда это новый вызов, вы выполняете вычисления - и в этом случае большинство или все рекурсивные вызовы будут в таблице. Например:

import sys
sys.setrecursionlimit(30000)

memo = {}

def ack(m, n):
    if not (m, n) in memo:
        result = (n + 1) if m == 0 else (
            ack(m-1, 1) if n == 0 else ack(m-1, ack(m, n-1)))
        memo[(m, n)] = result
    return memo[(m, n)]

print ack(3, 4)
print ack(4, 1)
print ack(4, 2)

Вы по-прежнему будете иметь проблемы с чем-либо большим, чем ack (4, 2), из-за использования памяти.

125
65533
Segmentation fault (core dumped)

Answer 2

Да. Можно использовать sys.setrecursionlimit и больше математики, чтобы улучшить алгоритм. См. Задачу Rosetta Code для кода Python.

Заметка!

Я просто перезапустил ack2:

%timeit a2 = ack2(4,2)
1000 loops, best of 3: 214 µs per loop

len(str(a2))
Out[9]: 19729

Это почти двадцать тысяч цифр в ответе.