练习 1.10¶

先将 Ackermann 函数的定义敲下来：

;;; 10-ackermann.scm

(define (A x y)
    (cond ((= y 0)
            0)
          ((= x 0)
            (* 2 y))
          ((= y 1)
            2)
          (else
            (A (- x 1)
               (A x (- y 1))))))

然后使用 A 函数对题目给定的几个表达式求值：

1 ]=> (load "10-ackermann.scm")

;Loading "10-ackermann.scm"... done
;Value: a

1 ]=> (A 1 10)

;Value: 1024

1 ]=> (A 2 4)

;Value: 65536

1 ]=> (A 3 3)

;Value: 65536

接着，我们通过给定一些连续的 n ，来观察题目给出的几个函数，从而确定它们的数学定义。

首先是 (define (f n) (A 0 n)) ：

n	0	1	2	3	4	5	6	7	...
值	0	2	4	6	8	10	12	14	...

可以看出，函数 f 计算的应该是 \(2 * n\) 。

然后是 (define (g n) (A 1 n)) ：

n	0	1	2	3	4	5	6	7	...
值	0	2	4	8	16	32	64	128	...

可以看出，函数 g 计算的应该是 \(2^n\) 。

最后是 (define (h n) (A 2 n)) ：

n	0	1	2	3	4	5	6	7	...
值	0	2	4	16	65536	...	...	...	...

当 n 超过 4 之后，再调用函数 h 就会出现超出解释器最大递归深度的现象，从仅有的几个计算结果来看，猜测函数 h 计算的应该是连续求 \(n\) 次二次幂，也即是 \({2^2}^{{\cdot}^{{\cdot}^2}}\)

Navigation

练习 1.10¶

讨论 ¶

Navigation