使用 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 时，我都会递减 'count' 变量，并且在第一次递归调用期间 (lastLessHelper (car lst) elem count) 它会正确递减，但是当调用 returns 并且它在 cdr lst 上递归：(lastLessHelper (cdr lst) elem count))] 'count' returns 的值到它的原始值。

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

如何在递归调用中保持'count'的值？我应该注意，可能有更简单的方法来做到这一点，但这是一项家庭作业，我们被禁止使用 'reverse' 调用。

编辑：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

如您所见，我们在 car 的递归中使用 count 并在 cdr 的递归中使用 return 值作为 count .

Answer 2

您甚至 不需要 计数器变量或辅助过程，只需 return 每个部分结果，然后累积递归调用的子结果。试试这个，使用遍历列表列表的标准模板：

(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

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

Using Scheme, how to keep a variable's value during recursive calls (nested lists)?

recursion

scheme