[SICP][1.10]Ackermann函数

先上维基百科： 维基百科：阿克曼函数

http://zh.wikipedia.org/wiki/%E9%98%BF%E5%85%8B%E6%9B%BC%E5%87%BD%E6%95%B8

阿克曼函数是非原始递归函数的例子；它需要两个自然数作为输入值，输出一个自然数。它的输出值增长速度非常高，仅是(4,3)的输出已大得不能准确计算。

1920年代后期，数学家大卫·希尔伯特的学生Gabriel Sudan和威廉·阿克曼，当时正研究计算的基础。Sudan发明了一个递归却非原始递归的Sudan函数。1928年，阿克曼又独立想出了另一个递归却非原始递归的函数。他最初的念头是一个三个变量的函数A(m,n,p)，使用康威链式箭号表示法是m→n→p。阿克曼证明了它是递归函数。希尔伯特在On the Infinite猜想这个函数不是原始递归。阿克曼在On Hilbert’s Construction of the Real Numbers证明了这点。后来Rozsa Peter和Raphael Robinson定义了一个类似的函数，但只用两个变量。

已知Ackerman函数akm(m,n)定义如下： 当m=0时: akm(m,n) = n + 1; 当m!=0, n=0时: akm(m,n) = akm(m-1, 1); 当m!=0, n!=0时: akm(m,n) = akm(m-1, akm(m, n-1));

Scheme 实现如下：

运行结果如下： 计算(A 4 3)的时候 程序就已经死了。只有中断。

当计算(A 1 10)时过程如下： (A 1 10) (A 0 (A 1 9)) (A 0 (A 0 (A 1 8) ………… (A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0 1)))))))))) (A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0 2))))))))) (A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0 4)))))))) …………. (A 0 2^9) 2^10 = 1024 此过程中调用了 A 十次。 当计算(A 2 4)时计算过程如下： (A 2 4) (A 1 (A 2 3)) (A 1 (A 1 (A 2 2))) (A 1 (A 1 (A 1 (A 2 1)))) (A 1 (A 1 (A 1 2))) (A 1 (A 1 (A 0 (A 1 1)))) (A 1 (A 1 (A 0 2))) (A 1 (A 1 4)) ……4次调用 (A 1 16) ……16次调用 2 ^16 = 65536 经过了20次调用

(A 3 3) (A 2 (A 3 2)) (A 2 (A 2 (A 3 1))) (A 2 (A 2 2)) (A 2(A 1 (A 2 1))) …… (A 2 4) …… 2 ^16 up主已经无法计算调用了多少次这个函数类了 - -

所以最后结论可以做出来了：

(define ( f n) (A 0 n)) 计算的是 2n (define (g n) (A 1 n)) 计算的是2^n (define (h n) (A 2 n)) 计算的是((….(((2^2)^2)^2)….)^2) n层嵌套。