## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.43

## Problem

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 <math>f(f(\cdots(f(x))\cdots))</math>. For example, if
*f* is the function <math>x \mapsto x + 1</math>, then the *n*th repeated application of *f* is the function <math>x \mapsto x + n</math>. 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 <math>2^n</math>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)

which should evaluate to 625.

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

## Solution

We know that `repeated` must ultimately return a lambda function of one argument. Here's an iterative implementation of procedure `repeated`. It builds the requested function by repeatedly composing its function argument, `f`, with the cumulative composition of previous iterations. The iteration is seeded with `f` itself.

(define (compose f g) (lambda (x) (f (g x)))) (define (inc x) (+ x 1)) (define (repeated f n) (define (repeated-iter i result) (if (= i n) result (repeated-iter (inc i) (compose f result)))) (repeated-iter 1 f))

Test:

(define (square x) (* x x)) ((repeated square 2) 5)

*Output:*

`
`

625

((repeated inc 3) 7)

*Output:*

`
`

10