尾遞歸？

我正在寫一個函數，它接受一個列表並返回列表中所有項目的平方和。稱爲上（1 2 3）它應該返回14：（1 + 2 + 3 ）。尾遞歸？

我有這個sqsum功能：

(define (sqsum lis) 
    (if (null? lis) 
     0 
     (+ (* (car lis) (car lis)) (sqsum (cdr lis))) 
    ) 
)

這是尾遞歸？我認爲這是遞歸的，但不是尾遞歸。這是我家庭作業的一部分，我不在尋找解決方案：我只想知道這是否是遞歸的尾部遞歸。如果沒有，那麼我需要閱讀更多並找到新的解決方案。

來源

2011-09-11 krunarsson

只是問自己這個函數的最後一個操作將是什麼它返回之前 - 是它sqsum通話或者是+？ – Carsten

要尾遞歸遞歸具有在最後的功能的情況發生，即你不能這樣做從recursiv調用的結果什麼。在這裏你將它傳遞給+，這使得它不是尾遞歸。儘管如此，編譯器可以優化這一點，而且自己也很容易做到。

來源

2011-09-11 17:34:07 nulvinge

（定義（sqsum X）（定義（FXS）（如果（空？x）的小號（F（CDR X）（+（*（車X）（車X））S））））（FX 0））這將是尾遞歸？ – krunarsson

我會這麼認爲。 – nulvinge

另請參閱：http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 – dyoo

不，它不是尾遞歸。

的一般方法制備的非尾遞歸函數尾遞歸是包括一個蓄能器，它是通過您的遞歸調用進行的程序的當前評估一個額外的參數。

順便說一句，這也是「助手」功能非常有用的地方。一般的做法是定義功能，使得它不採取累加器，在其中定義一個輔助函數確實採取蓄，再有主要功能不小，除了調用輔助函數。你會在一秒鐘內看到我的意思。

在你的情況（如果我記得正確我的計劃：P）：

(define (sqsum lis) 
    (define (sqsum-h lis acc) 
     (if (null? lis) 
      acc 
      (sqsum-h (cdr lis) (+ acc (* (car lis) (car lis)))) 
     ) 
    ) 
    (sqsum-h lis 0) 
)

這是尾遞歸，因爲過去的事情任何遞歸調用不會立即返回另一個函數的結果，而無需修改它。

來源

2011-12-15 03:36:57 koschei

回答

相關問題