理论上能否优化Ackermann函数？其时间复杂度可降低吗？

我出于好奇想知道，有没有时间复杂度比标准实现更优的Ackermann函数写法——这不是作业，纯粹是个人兴趣。我清楚Ackermann函数递归深度极大，除了做性能基准外没实际用途，而且数值增长快到离谱，我完全不关心计算出的具体结果。

Python 3不会有整数溢出问题，但时间有限，我先根据维基百科的定义实现了一个版本，只算了极小值验证输出正确：

def A(m, n):
    if not m:
        return n + 1
    return A(m - 1, A(m, n - 1)) if n else A(m - 1, 1)

这完全是定义的直接转译，但速度慢得离谱，我不知道该怎么优化，难道这个函数根本没法优化？

我首先想到的是记忆化（memoization），但递归是反向进行的，每次递归调用的参数之前都没出现过——参数是递减而非递增的，所以首次调用新参数时，记忆化完全帮不上忙。只有再次调用相同参数时，才能读取缓存结果，但只要输入(m,n)≥(4,2)，解释器还是会直接崩溃。

我还照着Stack Overflow上的一个回答实现了另一个版本：

def ack(x, y):
    for i in range(x, 0, -1):
        y = ack(i, y - 1) if y else 1
    return y + 1

结果这个版本速度更慢：

In [2]: %timeit A(3, 4)
1.3 ms ± 9.75 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [3]: %timeit ack(3, 4)
2 ms ± 59.9 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

补充测试结果 #

A(3,9)和A(4,1)会直接导致解释器崩溃，A(3,8)的性能测试如下：

In [2]: %timeit A(3, 8)
432 ms ± 4.63 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [3]: %timeit ack(3, 8)
588 ms ± 10.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

进一步验证参数重复情况 #

我写了代码统计调用次数：

from collections import Counter
from functools import cache

c = Counter()
def A1(m, n):
    c[(m, n)] += 1
    if not m:
        return n + 1
    return A(m - 1, A(m, n - 1)) if n else A(m - 1, 1)

def test(m, n):
    c.clear()
    A1(m, n)
    return c

发现参数确实会重复，但缓存对首次调用完全没用：

In [9]: %timeit Ackermann = cache(A); Ackermann(3, 4)
1.3 ms ± 10.1 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

只有再次调用相同参数时，缓存才发挥作用：

In [14]: %timeit Ackermann(3, 2)
101 ns ± 0.47 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

多次测试不同参数，首次调用都没有效率提升。

现在的核心问题是：理论上能否优化Ackermann函数？如果不能，能不能证明它的时间复杂度无法降低？

内容的提问来源于stack exchange，提问作者Ξένη Γήινος