使用Scheme，如何在递归调用（嵌套列表）期间保持变量的值？

Question

我试图从列表中删除最后一次出现的值，并且在嵌套列表的递归调用期间我的程序失败。

我有一个统计符号的出现次数的函数：

(define (countOccurrences lst elem count) 
    (cond 
    [(empty? lst)   count] 
    [(list? (car lst))  (countOccurrences (cdr lst) elem 
             (countOccurrences (car lst) elem count))] 
    [(equal? (car lst) elem) (countOccurrences (cdr lst) elem (add1 count))] 
    [else     (countOccurrences (cdr lst) elem count)])) 

和主体是在这里：

(define (lastLess lst elem) 
    (let ((count (countOccurrences lst elem 0))) 
    (if (< 0 count) 
     (lastLessHelper lst elem count) 
     lst))) 

辅助功能：

(define (lastLessHelper lst elem count) 
    (cond 
    [(empty? lst)   empty] 
    [(eq? count 0)  (cdr lst)] 
    [(eq? (car lst) elem) (set! count (sub1 count)) 
          (cond 
          [(eq? count 0) (cdr lst)] 
          [else   (cons (car lst) 
               (lastLessHelper (cdr lst) elem count))])] 
    [(list? (car lst)) (cons (lastLessHelper (car lst) elem count) 
           (lastLessHelper (cdr lst) elem count))] 
    [else     (cons (car lst) (lastLessHelper (cdr lst) elem count))])) 

的问题是这条线：

[(list? (car lst)) (cons (lastLessHelper (car lst) elem count) (lastLessHelper (cdr lst) elem count))] 

我递减“计数”变量每当(car lst)等于elem，并且所述第一递归调用(lastLessHelper (car lst) elem count)它正确地递减，但在当调用返回，并将其递归对CDR LST：(lastLessHelper (cdr lst) elem count))]“计数的值'返回到其原始值。

它适用于普通列表的输入，如(lastLess '(1 2 3 2 4 5) '2))我使用嵌套列表时作为输入，如(lastLess '(1 (2 3) 4 2 5) '2)返回(1 (2 3) 4 2 5)正确地得到(1 2 3 4 5)，但。

如何在递归调用期间保持'count'的值？我应该注意到，可能有更简单的方法来做到这一点，但这是一项家庭作业练习，我们被禁止使用“反向”呼叫。

编辑：Sylwester的评论帮助我理解。我的问题是不计算一个项目的发生，问题是要删除最后一个项目的发生。我的想法是首先计算该项目的出现次数，然后遍历列表并递减计数直到它为0，然后我会知道删除该项目，然后仅剩下列表的其余部分cons。

Answer 1

你永远不需要使用set!

(define (count-matches needle haystack) 
    ;; helper 
    (define (count-matches count haystack) 
    (cond ((equal? needle haystack) (+ count 1)) 
      ((pair? haystack) 
      (count-matches (count-matches count (car haystack)) 
          (cdr haystack))) 
      (else count))) 

    ;; call helper 
    (count-matches 0 haystack)) 

(count-matches 2 '(1 (2 3) 4 2 5)) ; ==> 2 

正如你看到的，我们使用count向递归在car并在cdr递归使用返回值作为count。

Answer 2

你甚至不需要需要一个计数器变量或帮助程序，只是返回每个部分的结果，并积累递归调用的子结果。试试这个，使用标准模板用于遍历一个列表的列表：

(define (count-matches ele lst) 
    (cond ((null? lst)    ; if the list is empty 
     0)       ; return default value 
     ((not (pair? lst))   ; if this is a single element 
     (if (equal? lst ele) 1 0)) ; check if it matches 
     (else      ; otherwise accumulate results of 
     (+ (count-matches ele (car lst))  ; the `car` part 
      (count-matches ele (cdr lst)))))) ; and the `cdr` part 

例如：

(count-matches 'x '(1 (x 2) 3 x (4 (5 x)) 6 (x))) 
=> 4