方案尾-递归/迭代

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))

我的问题是，这真的是迭代的吗？我相信我已经使用尾部递归正确地构建了它，但从技术上讲，它仍然将一系列操作推迟到count=0，在这里，它执行叠加的任意多个组合。

Answer 1

你提出了一个很好的问题。您从构建递归过程（（f（f（f（f...）））的递归过程（递归-重复）到构建相同递归过程的迭代过程（iter-重复）。

你认为你基本上做了同样的事情是对的，因为最终结果是一样的。你只是用两种不同的方式构造了同一个链。这是在你的实现中使用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