SICP Exercise 1.43

Question

If $f$ is a numerical function and $n$ is a positive integer, then we can form the $n$-th repeated application of $f$, which is defined to be the function whose value at $x$ is $f(f(\dots (f(x))\dots ))$.

For example, if $f$ is the function $x\mapsto x+1$, then the $n$-th repeated application of $f$ is the function $x\mapsto x+n$. If $f$ is the operation of squaring a number, then the $n$-th repeated application of $f$ is the function that raises its argument to the $2^n$-th power.

Write a procedure that takes as inputs a procedure that computes $f$ and a positive integer $n$ and returns the procedure that computes the $n$-th repeated application of $f$. Your procedure should be able to be used as follows:

copy((repeated square 2) 5)
625

Hint: You may find it convenient to use compose from exercise 1.42.

Answer

copy(define (square x) (* x x))

(define (compose f g)
  (λ (x) (f (g x))))

(define (repeated f n)
  (if (= n 1)
      (λ (x) (f x))
      (repeated (compose f f) (- n 1))))

((repeated square 2) 5)

Result:

copy625