Как переписать рекурсивную процедуру (повторение fn) как итеративный процесс с помощью Racket?

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