#P1695. 阿克曼(Ackmann)函数

阿克曼(Ackmann)函数

题目描述

阿克曼( AckmannAckmann )函数 AA ( mnm,n )中, mnm,n 定义域是非负整数,函数值定义为:

akm(m,n)={n+1(m=0)akm(m1,1)(m>0,n=0)akm(m1,akm(m,n1))(m,n>0)akm(m,n) = \begin{cases}n+1&(m=0)\\akm(m-1,1)&(m>0,n=0)\\akm(m-1,akm(m, n-1))&(m,n>0)\\\end{cases}

写出计算 Ack(mn)Ack(m,n) 的递归算法程序。

输入

两个非负整数 mmnn

输出

阿克曼函数 A(m,n)A(m,n) 的值。测试数据保证结果不超过 intint 范围,直接用递归不超时。

(提示:阿克曼函数的值增长速度非常高,仅是对于 A(4,2)A(4,2) 的输出就有 1972919729 位,而 A(4,3)A(4,3) 则即使是位数也不易估计。)

样例

输入数据 1

2 3

输出数据 1

9