|
|
首先，可以写出这个函数的函数式：
0, y = 0;
f(x,y) = 2y, x = 0;
2, y = 1;
f(x-1, f(x, y-1));
那么，对于 f(0,n), n>=0
当 n >= 1 时， f(0,n) = 2n ，
而当 n = 0 时， f(0,0) = 0 = 2*0， 也满足 2n ，
故 f(0,n) = 2n, n>=0.
对于f(1,n), n>=1
当 n > 1 时，有 f(1,n) = f(0, f(1, n-1)) = 2*f(1,n-1),
设 f(1,n) = 2^n
if n = 1, f(1,1) = 2 = 2^1
when n > 1, if f(1,n-1) = 2^(n-1)
then f(1,n) = 2*f(1,n-1) = 2*(2^(n-1)) = 2^n
故 f(1,n) = 2^n, n>0.
对于f(2,n), n>0
if n > 1 ,then f(2,n) = f(1, f(2, n-1)) = 2^f(2,n-1),
设 f(2,n) = 2^(2^(... (n 个 2)
if n = 1, then f(2,1) = 2
when n > 1, if f(2, n-1) = 2^(2^(... (n-1)
then f(2,n) = 2^f(2,n-1) = 2^(2^(
这样我们对于 (A 1 10) = 2^10 = 1024, (A 2 4) = 2^(2^(2^2)) = 2^16 = 65536
而 (A 3 3) = (A 2 A(3 2)) = A(2 A(2 A(2 1))) = (A 2 4) = 2^16 = 65536
(f n) = (A 0 n) = 2n
(g n) = (A 1 n) = 2^n
(h n) = (A 2 n) = 2^(2^(... (n个2)
---------------------------------------------
在网上可以找到关于 Ackermann 函数的讨论，主要是针对这个双递归如何用迭代来实现，Ackermann 函数是 德国数学家W.Ackermann 在1928年提出的。在 WikiPedia 英文版上可以搜索 Ackermann function
词条，有详细介绍，不过这个Ackermann function
略有不同。如下图：
|