recursion - 方案尾递归/迭代

Question

我在 scheme 中构建了一个递归函数，它将在某些输入上重复给定函数 f, n 次。

(define (recursive-repeated f n)
  (cond ((zero? n) identity)
        ((= n 1) f)
        (else (compose f (recursive-repeated f (- n 1))))))

我需要使用尾递归构建此函数的迭代版本，如果我正确理解尾递归，我认为我做对了。

(define (iter-repeated f n)
  (define (iter count total)
    (if (= count 0)
        total
        (iter (- count 1) (compose f total))))
  (iter n identity))

我的问题是，这实际上是迭代的吗？我相信我已经使用尾递归正确地构建了它，但它仍然在技术上推迟了一堆操作，直到计数 = 0，无论它堆叠了多少组合，它都会执行。

Answer 1

你提出了一个很好的问题。您从构建递归过程 ((f (f (f ...)))) 的递归过程 (recursive-repeated) 到迭代过程 (iter-repeated) 构建相同的递归过程。

您认为您基本上做了同样的事情是对的，因为最终结果是一样的。您只是以两种不同的方式构建了同一条链。这是在您的实现中使用 compose 的“结果”。

考虑这种方法

(define (repeat n f)
  (λ (x)
    (define (iter n x)
      (if (zero? n)
          x
          (iter (- n 1) (f x))))
    (iter n x)))

在这里，我们将返回一个等待输入参数的单个 lambda，而不是提前构建完整的函数调用链。指定输入参数后，我们将以迭代方式在 lambda 内部循环 n 次。

让我们看看它的效果

(define (add1 x) (+ x 1))

;; apply add1 5 times to 3
(print ((repeat 5 add1) 3)) ;; → 8