将列表的第一个元素递归地附加到列表的其余部分

Question

我对scheme很陌生，我想获得一个列表，比如（1 2 3 4），并将其发送给一个将返回（4 1 2 3）的函数。第二次运行将返回（3 4 1 2），依此类推，每次调用该函数都会创建一个右移列表。

解决这个问题的第一种方法是递归地交换列表的第一个和最后一个值。因此，在方案中，我会将列表的cdr附加到列表的car中，并递归地将列表的cdr发送回我的函数，直到只能进行最后一次交换。

然而，我不擅长创建递归函数，而且在用scheme等新语言创建递归函数时遇到了困难。到目前为止，这就是我试图给出的我想去哪里的想法。

(define (rShift lst)
  (if (null? lst)
      '()
      (append (cdr lst (car lst))(rShift (cdr lst)))))

Answer 1

您能做的最好的事情就是查看解释器的文档，看看有哪些列表函数可用，并使用它们构建解决方案。例如，在Racket中使用列表程序将实现一个简单的解决方案：

(define (rShift lst)
  (cons                             ; stick together the solution
   (last lst)                       ; pick the last item
   (take lst (sub1 (length lst))))) ; pick all items except the last one

让我们试一试：

(rShift '(1 2 3 4))
=> '(4 1 2 3)
(rShift (rShift '(1 2 3 4)))
=> '(3 4 1 2)

有无数种方法可以解决这个问题，我会让你找到最适合你需求的方法，但请记住，永远试着根据你已经掌握的构建块来解决问题，不要重新发明轮子。只是为了好玩，这里有另一种方法，使用reverse:

(define (rShift lst)
  (let ((rev (reverse lst)))
    (cons (car rev)
          (reverse (cdr rev)))))

Answer 2

如果你打算进行递归解决方案，那么你需要问自己"问题的哪一部分可以解决，剩下的是相同但较小的部分"和"我如何结束递归"。

对于您的问题，当您有最后一个元素时，您将结束递归，然后使用该元素将其添加到列表的前面。问题是，使用"右移"递归是不够的，因为你需要保留列表，以便将最后一个元素放在它的前面。

因此：

(define (right-shift list)
  (if (null? list)
      '()
      (let shifting ((list list) (result '()))
        (if (null? (cdr list))
            (cons (car list) (reverse result))
            (shifting (cdr list) (cons (car list) result))))))
;; Hey look, it compiles... gosh I love interactive languages.
;; ... and works.
> (right-shift '(1 2 3 4))
(4 1 2 3)
> (right-shift (right-shift '(1 2 3 4)))
(3 4 1 2)