一、什么是Ackerman函数（阿克曼函数）

定义：

$$A(m,n)=\{\begin{array}{ll}n+1& 若m=0\\ A(m-1,1)& 若m>0且n=0\\ A(m-1,A(m,n-1))& 若m>0且n>0\end{array}$$

或：

$$\{\begin{array}{ll}A(1,0)=2& m=0,n=1\\ A(2,m)=1& m\ge 0,n=0\\ A(n,0)=n+2& m=0,n\ge 2\\ A(n,m)=A(A(n-1,m),m-1)& m\ge 1,n\ge 1\end{array}$$

二、递归算法实现

1. 设计递归方程

当存在两个自变量时，应当先确定一个，然后再去研究关于另一个自变量的函数变化。

• 当$m=0$时
  • $A(m,n)=n+1$
• 当$m>0$时
  • 若$n=0$，则$A(m,n)=A(m-1,1)$
  • 若$n>0$，则$A(m,n)=A(m-1,A(m,n-1))$

2. 确定边界条件

此例为双重递归；其自变量为$m,n$，当$m<0且n<0$时跳出函数

3. 编写程序代码

// Ackermann函数（阿克曼函数）的递归实现算法
#include <iostream>

using namespace std;

int ackermann(int m, int n);

int main()
{
	int m, n = 0;

	cout << "请输入第一个数m(自然数)：";
	cin >> m;
	cout << "请输入第二个数n(自然数)：";
	cin >> n;

	cout << "A(m, n) = " << ackermann(m, n) << endl;

	return 0;
}

int ackermann(int m, int n)
{
	if (m == 0)
		return n + 1;
	else if (m > 0 && n == 0)
		return ackermann(m - 1, 1);
	else // else if (m > 0 && n > 0)
		return ackermann(m - 1, ackermann(m, n - 1));
}

4. 运行结果展示

---

*其它一些常见算法请参阅此链接~

---

最后，非常欢迎大家来讨论指正哦！