recursion - 检查列表的反向是否与未更改的列表相同？

Question

我正在学习方案，我必须做的一件事是递归以确定列表是否是反射的，即列表在颠倒时看起来是一样的。我必须原始地做，所以我不能对列表使用反向方法。我还必须使用显而易见的递归。问题是在方案中很难使用我们学到的非常基本的东西访问列表或缩短列表，因为它们有点像链表。我也想不使用索引。话虽如此，我有一些想法，想知道这些是否足够，你认为我实际上可以用方案的基础知识做得更好。

1. 使用递归(我的实现)反转列表并比较原始版本和此版本。列表。
2. 通过递归列表的其余部分来比较第一个和最后一个元素，以找到最后一个元素并与第一个元素进行比较。跟踪我递归了多少次，然后对列表的倒数第二个元素少做一次，以与列表的第二个元素进行比较。 (这做起来非常复杂，因为我已经尝试过但最终失败了，但我希望看到你们也会这样做)
3. 缩短列表以每次删除第一个和最后一个元素并进行比较。我不确定这是否可以使用方案的基础来完成。
4. 您的建议或提示或任何东西。我对计划很陌生。谢谢阅读。我知道它很长。

Answer 1

检查列表是否为回文而不反转它是 "There and Back Again" by Danvy and Goldberg 中解释的技术示例之一。 .他们在 (ceil (/(length lst) 2)) 递归调用中执行此操作，但有一个更简单的版本在 (length lst) 调用中执行此操作。

这是解决方案的框架:

(define (pal? orig-lst)
  ;; pal* : list -> list/#f
  ;; If lst contains the first N elements of orig-lst in reverse order,
  ;; where N = (length lst), returns the Nth tail of orig-lst.
  ;; Otherwise, returns #f to indicate orig-lst cannot be a palindrome.
  (define (pal* lst)
    ....)

  .... (pal* orig-lst) ....)

这听起来像是家庭作业，所以我不想填写所有的空白。