如何用Racket重写递归过程（重复f n）作为一个迭代过程？

Question

我的递归过程是这样的 (repeated f n) 该函数适用于 f n 次到一个论点。

(define (repeated f count)
  (if (= count 1)
      f 
      (lambda (x)
        (f ((repeated f (- count 1)) x)))))

例如： ((repeated sqr 3) 2) 返回256，即 (sqr(sqr(sqr 2))).

但我不知道如何实现 repeated 作为一个使用 Racket 的迭代过程。非常感谢任何建议。

Answer 1

将递归过程转换为迭代过程的典型解决方案是请一个累加器帮忙。

无论你用什么方式切入。repeated 将不得不返回一个过程。一个解决方案是使用一个名为 let 在返回的存储过程中，迭代 n 次，将结果记录在一个累加器中。这里是一个版本的 repeated 返回一个单价存储过程；请注意，这里没有输入验证，所以调用类似于 ((repeated f 0) 'arg) 会带来麻烦。

(define (repeated f n)
  (lambda (x)
    (let iter ((n n)
               (acc x))
      (if (= n 1) (f acc)
          (iter (- n 1)
                (f acc))))))

已命名的 let 表达式对于这样的事情非常方便，但是你也可以定义一个辅助过程来做同样的事情。我将把这个解决方案作为一个练习留给OP。

scratch.rkt> ((repeated sqr 3) 2)
256
scratch.rkt> ((repeated add1 8) 6)
14

Answer 2

我认为使用 for/fold 使溶液更清洁

(define ((repeated f n) x)
  (for/fold ([acc x]) ([i (in-range n)]) (f acc)))

使用它。

> ((repeated sqr 3) 2)
256
> ((repeated add1 8) 6)
14