CSP-S 提高级 · CSP 2022 提高级第一轮 第 15 题

ack 函数在输入参数“(2,2)”时的返回值为（）。

unsigned ack(unsigned m, unsigned n) {
    if (m == 0) return n + 1;
    if (n == 0) return ack(m - 1, 1);
    return ack(m - 1, ack(m, n - 1));
}

这题考递归函数阿克曼函数，双递归嵌套深，别一上来就硬算(2,2)。正确心法是：先算边界ack(0,n)=n+1，再算ack(1,n)的规律，最后用递推表从ack(1,4)倒推回ack(2,2)，由内向外、层层剥开。

最容易栽跟头的地方，就是把ack(2,2)直接展开，以为能一眼看出结果，结果嵌套层数爆炸，要么数漏要么数重。另一个坑是顺序搞反，先算外层ack(2,1)里的ack(2,0)时，忘了要先算最内层的ack(1,0)，导致整个链条断了。还有同学会误记ack(2,n)是2n+3，直接套公式算出2×2+3=7，碰巧对了，但万一题目改个参数就全错，必须按代码逻辑一步步推。

这道题考查的是递归函数，特别是阿克曼函数这种双递归（嵌套递归）的计算。阿克曼函数增长极快，但代码逻辑很单纯：m=0时返回n+1；n=0时把m减1、n置1再递归；否则把n减1递归，再把结果作为n传给上一层递归。命题人喜欢在这里挖坑，就是看你能不能在嵌套极深的情况下，依然保持清晰的计算顺序，不乱套公式、不硬算。

拿到题先想什么？别一上来就对着ack(2,2)狂按回车，那是死路。正确心法是：先找边界，再找规律，最后用递推表一步步上推。阿克曼函数的三个关键规律必须记牢：ack(0,n)=n+1（这是地基）；ack(1,n)=n+2（因为ack(1,n)=ack(0,ack(1,n-1))，展开后就是累加）；ack(2,n)=2n+3（这是本题要用的，但别直接套，要验证）。命题人爱考的就是让你从ack(1,4)倒推回ack(2,2)，看你是否真的理解递推过程，而不是死记硬背。

具体怎么算？从最小的参数开始递推。先算ack(0,n)：ack(0,0)=1, ack(0,1)=2, ack(0,2)=3……这是基础。再算ack(1,n)：ack(1,0)=ack(0,1)=2；ack(1,1)=ack(0,ack(1,0))=ack(0,2)=3；ack(1,2)=ack(0,ack(1,1))=ack(0,3)=4；ack(1,3)=5；ack(1,4)=6。这里有个细节：每层都要先算内层的ack(1,n-1)，再算外层的ack(0,…)，顺序不能乱。接着算ack(2,n)：ack(2,0)=ack(1,1)=3；ack(2,1)=ack(1,ack(2,0))=ack(1,3)=5；ack(2,2)=ack(1,ack(2,1))=ack(1,5)。现在需要算ack(1,5)：ack(1,5)=ack(0,ack(1,4))=ack(0,6)=7。所以ack(2,2)=7。

避坑提醒：最容易错的地方是直接把ack(2,2)展开，以为能一眼看出结果，结果嵌套层数爆炸，要么数漏要么数重。另一个坑是顺序搞反，先算外层ack(2,1)里的ack(2,0)时，忘了要先算最内层的ack(1,0)，导致整个链条断了。还有同学会误记ack(2,n)是2n+3，直接套公式算出2×2+3=7，碰巧对了，但万一题目改个参数就全错，必须按代码逻辑一步步推。另外，递归展开时记住三个要点——①由内向外先算最内层；②从边界条件m=0开始倒推；③用递推表逐步上推，不要试图一次性展开所有层。

考频与趋势：递归函数在题库中已考过115题，覆盖8个考试级别，从2007年到2026年分布极不均衡，2024年突然暴涨到25题，2025年也达15题，2026年18题，说明近年命题人明显加大了对递归和算法思维深度的考察力度。阿克曼函数作为递归的典型代表，虽然代码短小，但嵌套深、增长快，非常适合用来测试学生是否真正理解递归的本质，而不仅仅是会写递归代码。从历年数据看，这类题目在CSP提高级和NOIP提高组初赛中出现频率较高，且往往以单选题形式出现，要求快速判断返回值。

预测：基于2024-2026年递归题量激增的趋势，未来两年内阿克曼函数或其变种（如修改边界条件、调整参数顺序）仍可能作为单选题或填空题出现，重点考察学生能否在有限时间内理清递归展开顺序并正确计算返回值。若数据不足以支撑更具体的题型预测，则暂无足够依据预测，但递归深度与嵌套逻辑的考查方向大概率会延续。

综上，ack(2,2)的返回值是7，选B。