list - 如何对列表中的元素使用递归？

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 不是在 Scheme 中遍历列表的方法，因为通常你想使用递归，car，cdr 等
• 同样，递归调用在哪里？ compare 应该在某个时候被调用!

我相信这就是您的意图，它不是递归的，但它是实现该过程的最简单方法:

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

因为这看起来像是家庭作业，所以我只能给你一些从头开始解决问题的提示，而不是使用 apply。填空:

(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

注意我使用了一个命名的 let 来实现递归，所以 loop 是这里的递归过程:你可以看到 loop 是在 loop 中被调用。或者，您可以定义一个辅助程序。考虑到列表最初为空的特殊情况，我不得不这样做。

对于一般情况，递归是这样工作的:需要两个参数，prev 存储列表中的前一个元素，ls 存储列表的其余部分。在遍历的每个点，我们检查前一个和当前元素的谓词是否为假——如果是这样，那么我们返回假。如果不是，我们将使用新的 prev(当前元素)和列表的其余部分继续递归。我们一直这样做，直到列表为空，然后我们才返回 true。