如何對列表中的元素使用遞歸？

Question

我想在列表中使用遞歸，我需要通過所有元素。這是我的代碼：

(define compare 
    (lambda (ls pred?) 
    (if (null? list) 
     #f 
     (pred? (list-ref ls (- (length ls) 2)) (list-ref ls (- (length ls) 1)))))) 

但它只適用於最後兩個元素。結果應該是這樣的：

(compare '(1 2 3 4 5) <) -> #t 
(compare '(1 2 8 4 5) <) -> #f 

你知道我該怎麼辦嗎？

Answer 1

你是不是使用遞歸在代碼中的任何地方。事實上，它有錯誤，我認爲你沒有徹底測試它。例如：

• 的if條件應該是(null? ls)
• 使用list-ref不是穿越方案列表時，對於一般要使用遞歸，car，cdr等
要走的路
• 再次，遞歸調用在哪裏？應該在某個時候調用compare！

我相信這是您的本意，這不是遞歸，但它的實現過程最簡單的方法：

(define (compare ls pred?) 
    (apply pred? ls)) 

因爲這看起來像功課，我只能給你解決問題的一些提示從零開始，不使用apply。填充這一空白：我用了一個名爲let執行遞歸

(define (compare ls pred?) 
    (if <???>     ; special case: if the list is empty 
     <???>     ; then return true 
     (let loop ((prev <???>) ; general case, take 1st element 
       (ls <???>)) ; and take the rest of the list 
     (cond (<???>   ; again: if the list is empty 
       <???>)   ; then return true 
       (<???>   ; if pred? is false for `prev` and current element 
       <???>)   ; then return false 
       (else   ; otherwise advance the recursion 
       (loop <???> <???>)))))) ; pass the new `prev` and the rest of the list 

通知，所以loop是這裏的遞歸過程：你可以看到，loop被稱爲內loop。或者你可以定義一個幫助程序。考慮到列表最初爲空的特殊情況，我必須這樣做。

對於一般情況，遞歸的工作原理是這樣的：需要兩個參數，prev存儲列表中的前一個元素，ls列表的其餘部分。在遍歷中的每一點上，我們檢查謂詞對於前一個元素和當前元素是否爲假 - 如果是這種情況，那麼我們返回false。如果不是，我們繼續用新的prev（當前元素）和列表的其餘部分遞歸。我們繼續這樣下去，直到列表爲空，然後我們返回true。