將尾遞歸/迭代過程轉換爲完全遞歸過程

Question

我目前在Scheme中編寫一個簡單的程序，遞歸地將數字相加，而不使用+運算符。現在我有這個程序，它做什麼，我想做的事：

(define (add1 x) (+ x 1)) 

(define (sub1 x) (- x 1)) 

(define (plus x y) 
    (if (zero? y) 
     x 
     (plus (add1 x) (sub1 y)) 
    ) 
) 

然而，我的導師要我放下尾遞歸/迭代和寫加過程完全遞歸。沒有告訴我太多（畢竟，這是一個單一的練習），你能指出我在正確的方向弄清楚如何做到這一點？

在此先感謝！

Answer 1

我同意上司的評價，這是一個愚蠢的練習 - 你的答案是相當不錯，因爲，它已經是一個tail-recursive的解決方案，這比教師要求的解決方案（這也是遞歸更有效，但不是尾遞歸遞歸，完全調用遞歸是一種用詞不當）。無論如何，這裏有一個提示：

(define (plus x y) 
    (if (zero? y) ; the first part remains unchanged 
     x 
     <???>)) ; now, what do we put here? 

您在每個遞歸步驟必須add1，這個想法是，你不斷增加1正是y倍，並在最後您添加到x。讓我用一個例子說明這一點，添加4加3我們這樣做：

(plus 4 3) 

它擴展成這樣：

(add1 (plus 4 2)) 
(add1 (add1 (plus 4 1))) 
(add1 (add1 (add1 (plus 4 0)))) 
(add1 (add1 (add1 4))) 

在上面，4在註定要x和3到y開始，執行程序後我們看到add1被稱爲三次，第一次我們加1到4，然後1到5最後是1至6，直到我們獲得7。換句話說：遞歸步驟必須調用add1得到遞歸的結果調用plus，其中x保持不變，y遞減一個單位直到它達到零，此時我們達到基本情況，遞歸解除返回正確的結果。