recursion - 如何反转列表？

Question

Scheme中反转列表的功能是什么？
它需要能够处理嵌套列表。因此，如果您执行 (reverse '(a (b c d) e)) 之类的操作你会得到(e (b c d) a)作为输出。
我应该如何解决这个问题？我不只是在寻找答案，而是在寻找可以帮助我学习的东西。

Answer 1

(define (my-reverse ls)
  (define (my-reverse-2 ls acc)
    (if (null? ls)
      acc
      (my-reverse-2 (cdr ls) (cons (car ls) acc))))
  (my-reverse-2 ls '()))

这使用一个累加器变量来反转列表，从传入列表中取出第一个元素并将其放在累加器的前面。它隐藏了累加器获取函数，只公开了获取列表的函数，因此调用者不必传入空列表。这就是为什么我有 my-reverse-2。

(my-reverse-2 '(a (b c d) e) '()); will call
(my-reverse-2 '((b c d) e)  '(a)); which will call
(my-reverse-2 '(e)  '((b c d) a)); which will call
(my-reverse-2 '() '(e (b c d) a)); which will return
'(e (b c d) a)

因为 my-reverse-2 中的最后一个函数调用调用my-reverse-2 ，返回值直接传递(第一次调用的返回值就是第二次调用的返回值，以此类推)my-reverse-2是尾部优化的，这意味着它不会用完堆栈上的空间。因此，只要您愿意，就可以使用列表来调用它。

如果您希望它应用于嵌套列表，请使用以下内容:

(define (deep-reverse ls)
  (define (deep-reverse-2 ls acc)
    (if (null? ls)
        acc
        (if (list? (car ls))
            (deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc))
            (deep-reverse-2 (cdr ls) (cons (car ls) acc)))))
  (deep-reverse-2 ls '()))

这会在将元素添加到列表之前检查元素是否为列表，如果是，则首先将其反转。
由于它调用自身来反转内部列表，它可以处理任意嵌套。
(deep-reverse '(a (b c d) e)) -> '(e (d c b) a)尽管存在嵌套列表，但它是按字母倒序排列的。
它评估如下:

(deep-reverse-2 '(a (b c d) e) '()); Which calls
(deep-reverse-2 '((b c d) e)  '(a))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d)  '(b)) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d)  '(c b)) '(a)))
(deep-reverse-2 '(e) (cons '(d c b) '(a)))
(deep-reverse-2 '(e)  '((d c b) a))
(deep-reverse-2 '() '(e (d c b) a))
'(e (d c b) a)