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(\ldots(f(x))\ldots))\).

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:

((repeated square 2) 5)
625

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

Answer

(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:

625