SICP 习题 （1.10）解题总结
SICP 习题 1.10 讲的是一个叫“Akermann函数”的东西，去百度查可以查到对应的中文翻译，叫“阿克曼函数”。
就像前面的解题总结中提到的，我是一个数学恐惧者，看着稍微复杂一点的什么函数我就怕。所以这道题放了很久都没去动它，不过有担心跳过这道题对后面的学习不利，所以最终还是鼓足勇气尝试做这个题目。
做完了我才发现，其实这道题真的可以跳过，做不做这道题似乎对后面的学习没什么影响。从题目的内容来看，作者应该是希望在习题中引入“树形递归”，让学生在下一节课的学习中有所准备，相当于是预习题。事实上，这个“预习题”太难了，比后面介绍的“斐波那契数”难好多，所以起不到什么“预习”的作用。
所以，如果你也害怕数学的话，可以考虑跳过这道题，就当它从来没有在你生命中出现过。
当然，如果你愿意挑战自己，和我一样尝试一下，你也会发现其实所谓的“阿克曼函数”也没什么太神秘的。
大家都说数学是“大脑的体操”，我没有数学天分，做不了“大脑的体操”，不过我慢慢爬上去，看看“大脑的单杠”啥样子还是可以的嘛。
先看看“阿克曼函数”的Scheme定义：
(define (A-with-info x y) (format #t "Evaluating (A ~S ~S) " x y) (cond ((= y 0) (format #t "the result is 0~%"))((= x 0) (format #t "the result is ~S~%" (* 2 y)))((= y 1) (format #t "the result is 2~%"))(else (format #t "transforming to (A ~S (A ~S ~S))~%" (- x 1) x (- y 1)))) (cond ((= y 0) 0)((= x 0) (* 2 y))((= y 1) 2)(else (A-with-info (- x 1) (A-with-info x (- y 1))))))
以上代码几乎完全和(A x y)的代码一样，就是增加了一些format的输出而已，这样可以在代码运行过程中跟踪过程的变换。
比如，调用(A-with-info 1 8)的结果如下，通过以下输出可以比较明了地看清过程的变换。
1 ]=> (A-with-info 1 8)
Evaluating (A 1 8) transforming to (A 0 (A 1 7))
Evaluating (A 1 7) transforming to (A 0 (A 1 6))
Evaluating (A 1 6) transforming to (A 0 (A 1 5))
Evaluating (A 1 5) transforming to (A 0 (A 1 4))
Evaluating (A 1 4) transforming to (A 0 (A 1 3))
Evaluating (A 1 3) transforming to (A 0 (A 1 2))
Evaluating (A 1 2) transforming to (A 0 (A 1 1))
Evaluating (A 1 1) the result is 2
Evaluating (A 0 2) the result is 4
Evaluating (A 0 4) the result is 8
Evaluating (A 0 8) the result is 16
Evaluating (A 0 16) the result is 32
Evaluating (A 0 32) the result is 64
Evaluating (A 0 64) the result is 128
Evaluating (A 0 128) the result is 256
;Value: 256
如果你愿意花时间，可以想一些办法让上面的输出更清晰一些，比如我写的另一个过程(A-with-detail）的输出如下：
1 ]=> (A-transformer 1 8 "" "")
(A 1 8)
(A 0 (A 1 7))
(A 0 (A 0 (A 1 6)))
(A 0 (A 0 (A 0 (A 1 5))))
(A 0 (A 0 (A 0 (A 0 (A 1 4)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 1 1) is 2])))))))
(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 2) is 4]))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))
(A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 4) is 8])))))
(A 0 (A 0 (A 0 (A 0 (A 0 8)))))
(A 0 (A 0 (A 0 (A 0 [(A 0 8) is 16]))))
(A 0 (A 0 (A 0 (A 0 16))))
(A 0 (A 0 (A 0 [(A 0 16) is 32])))
(A 0 (A 0 (A 0 32)))
(A 0 (A 0 [(A 0 32) is 64]))
(A 0 (A 0 64))
(A 0 [(A 0 64) is 128])
(A 0 128)
[(A 0 128) is 256]
;Value: 256
这里就可以清晰地看见(A 1 8)的展开和归约过程。
同样，我们可以看看(A 2 4)的变换过程：
1 ]=> (A-transformer 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 [(A 2 1) is 2])))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 [(A 1 1) is 2])))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 [(A 0 2) is 4]))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 [(A 1 1) is 2]))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 [(A 0 2) is 4])))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 [(A 0 4) is 8]))
(A 1 (A 0 8))
(A 1 [(A 0 8) is 16])
(A 1 16)
(A 0 (A 1 15))
(A 0 (A 0 (A 1 14)))
(A 0 (A 0 (A 0 (A 1 13))))
(A 0 (A 0 (A 0 (A 0 (A 1 12)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 1 7))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 1 1) is 2])))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 2) is 4]))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 4) is 8])))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 8) is 16]))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 16) is 32])))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 32) is 64]))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 64) is 128])))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 128) is 256]))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 256) is 512])))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 512) is 1024]))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))
(A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 1024) is 2048])))))
(A 0 (A 0 (A 0 (A 0 (A 0 2048)))))
(A 0 (A 0 (A 0 (A 0 [(A 0 2048) is 4096]))))
(A 0 (A 0 (A 0 (A 0 4096))))
(A 0 (A 0 (A 0 [(A 0 4096) is 8192])))
(A 0 (A 0 (A 0 8192)))
(A 0 (A 0 [(A 0 8192) is 16384]))
(A 0 (A 0 16384))
(A 0 [(A 0 16384) is 32768])
(A 0 32768)
[(A 0 32768) is 65536]
;Value: 65536
最后就是有关(A 2 n)的数学含义，仔细看看上面的变换过程大概可以想明白，就是2的右上角有n个不断变小的2，就是取2 的2次方，赋予A，然后取2的A次方，赋予B，再取2的B次方，赋予C，一直下去，做n次。从上面的分析看，这个“阿克曼函数”有迭代实现喔。是否还记得我们之前讨论过的“迭代计算过程”和“递归计算过程”？书中的“阿克曼函数”的实现使用的是“递归计算过程”，而这个函数显然有“迭代计算过程”的实现方法。有关这个我们在这里就不详细讨论了，另找时间再讲这个东西。
如果看完上面的内容不明白的话最好自己做完成以上步骤，应该会有一些认识。如果还是不明白就去看看网上有关“阿克曼函数”的具体解释，看了还是不明白的话就放弃吧，“数学不是个买卖，想买就能买”。
对于已经明白过来的同学们，可以想想(A 3 n)的数学含义是什么，有点花脑筋哟！想明白就再想想(A 4 n), (A 5 n)，想想(A m n)函数中m 和n分别起到什么作用，(A m n)的广泛含义是什么？
问完这些问题，我似乎看到了很多好学的同学们抓破脑袋毫无头绪的样子，于是我开心地笑了，愉快地关上了我的MacBook，深藏功与名。
