如何以遞歸方式獲取列表中的偶數元素

Question

我試圖創建一個函數，它將返回列表中偶數編號的元素。

例如：

(evens '(a b c d)) 

應該返回

(b d) 

下面的代碼似乎對於有列表和元素的奇數工作，但如果我給它與偶數的列表的元素，這是不正確的。

例如：

(evens '(a b c d e)) 

將返回

(b d) 

但是：

(evens '(a b c d)) 

將返回

(a c) 

有什麼想法？

改變了我的代碼：

(DEFINE (evens lis) 
(cond 
    ((null? lis) '()) 
    (else (cons (cadr lis) (evens (cdr lis)))) 
    )) 

得到一個錯誤，說傳遞到安全車的對象不是一對？

Answer 1

的問題是，如果您的列表有偶數個元素中，modulo分公司匹配並開始cons在你的榜樣與列表的car荷蘭國際集團......因此，你得到的a，等等。

更重要的是，你並不需要使用length此功能...你不應該：因爲length需要線性時間列表的長度，evens現在需要二次的時間。

建議：您的程序應該'記住'它是否在每個遞歸步驟中的'奇數'或'偶數'位置......你怎麼能這樣做（有幾種方法）？

Answer 2

你的代碼很少缺少檢查和一些不正確的邏輯。

(define (evens lis) 
(cond 
    ((null? lis) '()) 
    ((eq? (cdr lis) '()) '()) ;missing condition 
    (else (cons (cadr lis) (evens (cddr lis)))))) ; it is cddr not cdr 

Answer 3

同樣的問題已經被問time和again在過去的幾天。我會直接回答這個時候，直設置：

(define (evens lst) 
    (if (or (null? lst)    ; if the list is empty 
      (null? (cdr lst)))  ; or the list has a single element 
     '()       ; then return the empty list 
     (cons (cadr lst)   ; otherwise `cons` the second element 
      (evens (cddr lst))))) ; and recursively advance two elements 

這裏是如何做到的一些錯誤首先檢查：

(define (find-evens lst) 
    (if (list? lst) 
     (evens lst) 
     (error "USAGE: (find-evens [LIST])"))) 

Answer 4

我要回答與評論的例子你的問題希望你能真正學到一些東西，而不是僅僅給出可行的代碼。實際上，假設你對計劃不熟悉，看幾段代碼可能會更有啓發性。

您最初的定義是這樣的：

(define (evens lis) 
    (cond (;; Check: Recursion stop condition 
     (null? lis) 
     '()) 
     (;; Wrong: Calling length at each step => O(n^2) 
     ;; Wrong: Assuming even element if list has even number of elements 
     (= (modulo (length lis) 2) 0) 
     ;; Wrong: Recursing with the rest of the list, you'll get odds 
     (cons (car lis) (evens (cdr lis)))) 
     (else 
     ;; Wrong: Recursing with the rest of the list with cdr, you'll get odds 
     (evens (cdr lis))))) 

之後，編輯完你的問題將其更新爲這樣的事情：

(define (evens lis) 
    (cond (;; Check: Recursion stop condition 
     (null? lis) 
     '()) 
     (else 
     ;; Check: Building list with second element 
     ;; Wrong: If lis only has 1 element, 
     ;;  (cdr lis) is null and (car (cdr list)) is an error. 
     (cons (cadr lis) 
       ;; Wrong: Recursing with cdr, you'll get odds 
       (evens (cdr lis)))))) 

一個解決辦法是檢查列表有至少第二個元素：

(define (evens lis) 
    (cond (;; Check: Recursion stop condition 1 
     (null? lis) 
     '()) 
     (;; Check: Recursion stop condition 2: list of length = 1 
     (null? (cdr lis)) 
     '()) 
     (else 
     ;; Check: Building list with second element 
     ;; The previous cond clauses have already sorted out 
     ;; that lis and (cdr lis) are not null. 
     (cons (cadr lis) 
       ;; Check: Recurse "the rest of the rest" of lis with cddr 
       (evens (cddr lis))))) 

練習：使用if和or將此解決方案簡化爲只有2個分支。