Scheme的尾递归/迭代

Question

我在Scheme中编写了一个递归函数，它可以对某个输入重复n次执行给定的函数f。

(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，其中它执行了多少个组合。

- Eddie V

---

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Sorawee Porncharoenwase

没错，但我想说的是，当你返回total时，它返回了一堆操作，比如`(compose square (compose square (compose square (identity x))))`它在返回total时进行评估，而不是在尾调用发生时进行评估。或者我是不是想得太多了？ - Eddie V

@EddieV 在调用函数之前，所有传递给函数的参数都会被求值。 - molbdnilo

我明白了。嗯，那么我猜这就有道理了，谢谢！ - Eddie V

虽然它是迭代的，但最终返回的是一个笨重的lambda嵌套。Noamik在下面的答案中给出了一种无需混乱的方法。 - WorBlux

Answer 1

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

你的想法是正确的，因为最终结果是相同的。你只是用两种不同的方式构建了相同的链条。这是在实现中使用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

- Mulan