实现阿克曼函数时两次递归代码为何一次触发递归深度超限？

AI 小北

2026-5-11

为什么第一段阿克曼函数代码会触发递归深度超限，而第二段不会？

咱们先把阿克曼函数的明确定义摆出来，方便对比：

a(0,m) = m+1
a(n+1,0) = a(n,1)
a(n+1,m+1) = a(n,a(n+1,m))

第一段代码的致命错误

先看你第一次写的代码：

def a(n,m):
    if n == 0:
        return m + 1
    elif m == 1:  # 这里完全写错了！
        return a(n ,0)
    else:
        return a(n - 1, a(n, m - 1))

你把定义里处理m=0的分支，错误写成了m==1的判断。这会直接导致逻辑崩盘，举个简单的测试例子：比如调用a(1,0)。

按照阿克曼函数的定义，a(1,0)应该等于a(0,1)，也就是1+1=2。但在第一段代码里：

n=1≠0，m=0≠1，所以直接进入else分支，执行a(0, a(1, -1))
接下来调用a(1,-1)，同样n≠0、m≠1，又进入else分支，变成a(0, a(1,-2))
以此类推，m会不断减1，变成-3、-4……永远碰不到终止条件（n==0或者m==1），无限递归下去，直到Python触发递归深度超限的报错。

第二段代码的正确逻辑

再看你修正后的代码：

def a(n,m):
    if n == 0:
        return m + 1
    elif m == 0:  # 这里完美对应了定义
        return a(n-1 , 1)
    else:
        return a(n - 1, a(n, m - 1))

这段代码完全贴合阿克曼函数的三个定义：

当n=0时，直接返回m+1，这是最底层的终止条件；
当m=0时，调用a(n-1,1)，正好对应定义里的a(n+1,0)=a(n,1)（反过来就是a(n,0)=a(n-1,1)，适用于n>0的情况）；
其他情况执行a(n-1,a(n,m-1))，对应定义里的a(n+1,m+1)=a(n,a(n+1,m))（替换变量后就是这个形式）。

每一步递归都会让问题的规模缩小：要么n减1，要么m减1，最终一定会触碰到n=0的终止条件，自然不会出现无限递归的问题。