-2

我试图让一个非尾递归函数返回列表的最后一个元素，而不使用任何类型的反向、映射、迭代、突变（内置或用户构建）。到目前为止，我已经成功地制作了一个尾递归版本和一个使用反向函数的非尾版本。但我只是想不出如何制作一个非尾递归函数。

我真的很感谢你的帮助！

4

2 回答 2

3

想象一下，你有这样的尾递归版本：

(define (last-element lst)
  (if base-case-expression
      result-expression
      recursion-expression))

现在为了不让它尾递归，你只需让你的函数对结果做一些事情。例如。将其缓存在绑定中，然后返回：

(define (last-element lst)
  (if base-case-expression
      result-expression
      (let ((result recursion-expression))
        result)))

这里递归调用不是尾部位置。然而，一个足够聪明的编译器可能会使编译后的代码是尾递归的。例如。许多 Scheme 实现将代码转换为连续传递样式，然后每个调用都变成了尾调用，并且堆栈被不断增长的闭包所取代。这两个版本的结果将非常相似。

于 2021-10-03T02:48:08.760 回答
3

注意：出于某种原因，我使用 Common Lisp 编写了这个答案，然后才注意到该问题被标记为、和。在任何情况下，Common Lisp 都属于后者，并且代码很容易适应 Scheme 或 Racket。

对于非尾递归的函数，您需要放置递归调用，使它们不在尾位置，即，在返回之前不需要对递归调用的结果进行进一步的操作。因此，您需要一种递归策略来获取列表的最后一个元素，该元素对递归调用的结果进行进一步的操作。

一种策略是在从基本情况返回的路上建立一个“反向列表”，同时将该列表分开，以便在最后留下所需的结果。这是一个reversal无需拆开任何东西即可展示想法的功能：

(defun reversal (xs)
  (if (cdr xs)
      (cons (reversal (cdr xs)) (car xs))
      xs))

上面的函数用输入列表的元素反向构建一个嵌套的点列表：

CL-USER> (reversal '(1 2 3 4 5))
(((((5) . 4) . 3) . 2) . 1)

现在，car可以在此结果上多次调用该函数以获取输入的最后一个元素，但我们可以在构造新列表时这样做：

(defun my-last (xs)
  (car (if (cdr xs)
           (cons (my-last (cdr xs)) (car xs))
           xs)))

这里my-last调用后调用函数(trace my-last)：

CL-USER> (trace my-last)
(MY-LAST)
CL-USER> (my-last '(1 2 3 4 5))
  0: (MY-LAST (1 2 3 4 5))
    1: (MY-LAST (2 3 4 5))
      2: (MY-LAST (3 4 5))
        3: (MY-LAST (4 5))
          4: (MY-LAST (5))
          4: MY-LAST returned 5
        3: MY-LAST returned 5
      2: MY-LAST returned 5
    1: MY-LAST returned 5
  0: MY-LAST returned 5
5

该解决方案需要对调用的结果进行两次操作my-last，即，cons和car。优化器似乎确实有可能注意到car正在调用 a 的结果cons，并优化my-last为：

(defun my-last-optimized (xs)
  (if (cdr xs)
      (my-last-optimized (cdr xs))
      (car xs)))

如果是这种情况，那么优化的代码将是尾递归的，然后可以应用尾调用优化。我不知道是否有任何 lisp 实现可以进行这种优化。

另一种策略是存储原始列表，然后在使用cdr. 这是使用辅助函数的解决方案：

(defun my-last-2 (xs)
  (car (my-last-helper xs xs)))

(defun my-last-helper (xs enchilada)
  (if (cdr xs)
      (cdr (my-last-helper (cdr xs) enchilada))
      enchilada))

这也按预期工作。这是一个示例，再次trace用于查看函数调用。这一次两者都my-last-2和my-last-helper已经traced：

(trace my-last-2 my-last-helper)
(MY-LAST-2 MY-LAST-HELPER)
CL-USER> (my-last-2 '(1 2 3 4 5))
  0: (MY-LAST-2 (1 2 3 4 5))
    1: (MY-LAST-HELPER (1 2 3 4 5) (1 2 3 4 5))
      2: (MY-LAST-HELPER (2 3 4 5) (1 2 3 4 5))
        3: (MY-LAST-HELPER (3 4 5) (1 2 3 4 5))
          4: (MY-LAST-HELPER (4 5) (1 2 3 4 5))
            5: (MY-LAST-HELPER (5) (1 2 3 4 5))
            5: MY-LAST-HELPER returned (1 2 3 4 5)
          4: MY-LAST-HELPER returned (2 3 4 5)
        3: MY-LAST-HELPER returned (3 4 5)
      2: MY-LAST-HELPER returned (4 5)
    1: MY-LAST-HELPER returned (5)
  0: MY-LAST-2 returned 5
5

在这种情况下，递归调用my-last-2return 后唯一需要的操作是cdr，但这足以防止它成为尾调用。

于 2021-10-03T18:08:52.213 回答