<< Previous exercise (1.42) | sicp-solutions | Next exercise (1.44) >>

Define some primitives:

         (define (square x) (* x x)) 
         (define (compose f g) (lambda (x) (f (g x)))) 

Define the procedure:

 (define (repeat f n) 
    (if (< n 1) 
        (lambda (x) x) 
        (compose f (repeat f (- n 1))))) 

Test with:

         ((repeat square 2) 5) 



Another solution using the linear iterative way.

 (define (repeat f n) 
   (define (iter n result) 
     (if (< n 1) 
         (iter (- n 1) (compose f result)))) 
   (iter n identity)) 

Note: This is not linearly iterative as described in the book as a chain of deferred operations is still being built.

The above answer does not follow the book's instructions. The book instructs "Write a procedure that takes as inputs a procedure that computes f and a positive integer n and returns the procedure that computes the nth repeated application of f." A correct answer is as follows:

 (define (repeated f n) 
   (lambda (x) (cond ((= n 0) x) 
                      ((compose (repeated f (- n 1)) f) x))))) 

I think the following solution is more elegant. When we only need to apply the function once, we can just return the function (I'm not doing error-checking here to see of n is smaller than 1).

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

An extremely succinct solution uses the accumulate procedure defined in 1.32:

 (define (repeated f n) 
   (accumulate compose identity (lambda (i) f) 1 inc n)) 

An solution with O(log n) complexity using compose:

 (define (repeated f n) 
   (cond ((= n 0) identity) 
         ((even? n) (repeated (compose f f) (/ n 2))) 
         (else (compose f (repeated f (- n 1))))))