使用尾端递归重写一个通用函数

Question

我一直在尝试修改此代码以使用尾端递归重写“重复”函数，但在我的尝试中遇到了一些困难。

(define (repeat n x)
  (if (= n 0)
      '()
      (cons x (repeat (- n 1) x))))

这是原来的“重复”功能。它遍历 'n - 1' 级递归，然后在 'n' 次递归调用中将 'x' 附加到列表中。取而代之的是，应该进行递归调用，并且 'x' 应该同时附加到列表中。

(define (repeat-tco n x)
  (trace-let rec ([i 0]
                  [acc '()])
    (if (= i n)
        acc
        (rec (+ i 1) (cons x acc)))))

这是我想出的最接近的重写版本，我相信它遵循尾调用递归，但我不完全确定。

Answer 1

你的 repeat-tco 函数确实是尾递归的：之所以如此是因为对 rec 的递归调用在 'tail position' 中：在它被调用的地方，调用的函数除了 return 该调用的值外，它别无他法。

[以下只是一些可能有用的东西：答案在上面，但是本质上'yes'的答案似乎太短了。]

采用过程 p 积累一些结果的技巧，比如 (cons ... (p ...)) 并将其转换为带有额外 'accumulator' 参数的过程，然后尾递归常见的。使用此技术的结果是结果倒退：这对您来说无关紧要，因为列表中的所有元素都是相同的，但想象一下：

(define (evens/backwards l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        es
        (loop (rest lt)
              (if (even? (first lt))
                  (cons (first lt) es)
                  es)))))

这将 return 其参数的偶数元素，但向后。如果您希望他们以正确的方式解决问题，糟糕的答案是

(define (evens/terrible l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        es
        (loop (rest lt)
              (if (even? (first lt))
                  (append es (list (first lt)))
                  es)))))

（为什么这是一个糟糕的答案？）正确答案是

(define (evens l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        (reverse es)
        (loop (rest lt)
              (if (even? (first lt))
                  (cons (first lt) es)
                  es)))))

使用尾端递归重写一个通用函数

Rewriting a common function using tail-end recursion

lisp

recursion

tail-recursion

racket