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：阿克曼的功能

回答

相關問題