SICP练习1.10：阿克曼的功能

我通过Structure and Interpretation of Computer Programs工作和方案评价有关于锻炼1.10个问题，其中，使用被定义为SICP练习1.10：阿克曼的功能

(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 10)的价值。

现在，我知道答案应该是(A 1 10) = 2^10 = 1024，但通过计算工作时，我得到如下：

(A 1 10) 
(A (- 1 1) (A 1 (- 10 1))) 
(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 (A 0 (A 0 (A 0 0)))))))))))))

现在，我明白的方式，计划将首先评估最深的表情开始，即最右边的(A 0 0)。这具有值0，因为函数的第一个条件符合(= y 0)。下一步会发生同样的情况，我们最终会减少所有的括号，直到最后一个(A 0 0)，由于类似的原因，它们的值也会是0。现在，我得到的最后一行应该是这样的

(*2 (*2 (*2 (*2 (*2 (*2 (*2 (*2 (*2 (*2 (*2 (A 0 0)))))))))))))

所以，如果这一切是正确的，为什么最后(A 0 0)产量2代替0？或者，更一般地说，你能发现我推理中的错误在哪里吗？我很确定它或者对递归调用的评估过程或者对条件语句进行评估的方式有一定的作用。

解决：正如leppie注意到(= y 1)首先得到评估，获得2作为价值(A 0 1)前往(A 0 0)

来源

2014-09-24 Unayko

你有一个额外的步骤，其中y = 1，它产量2（我认为） – leppie 2014-09-24 08:50:32

哦，jeeze。我完全错过了。谢谢！ – Unayko 2014-09-24 08:51:42

之前，你永远不会一路去

(A 0 0)

扩张进行

(A 0 (A 1 9)) 
(A 0 (A 0 (A 1 8))) 
(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 1 1))))))))))

，现在(A 1 1)评估为2。

来源

2014-09-24 08:57:22

SICP练习1.10：阿克曼的功能

回答

相关问题