2

我正在尝试在列表中使用递归，我需要遍历所有元素。这是我的代码：

(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

你知道我应该怎么做吗？

4

1 回答 1

3

您没有在代码中的任何地方使用递归。事实上，它有错误，我认为你没有彻底测试过它。例如：

  • if条件应该是(null? ls)
  • 在 Scheme 中遍历列表时，使用list-ref不是要走的路，因为通常你想使用递归，，，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

Notice that I used a named let for implementing the recursion, so loop is the recursive procedure here: you can see that loop is being called inside loop. Alternatively you could've defined a helper procedure. I had to do this for taking into account the special case where the list is initially empty.

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

于 2012-11-24T12:42:01.120 回答