<< 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)
```

Output:

625

Another solution using the linear iterative way.

```
(define (repeat f n)
(define (iter n result)
(if (< n 1)
result
(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)
(else
((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)
f
(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))))))
```

A logarithmic iterative solution.

(define (lcompose f g) (lambda (x) (g (f x)))) (define (identity x) x) (define (repeated f n) (define (iter g h m) (cond ((= m 0) g) ((odd? m) (iter (lcompose g h) h (- m 1))) (else (iter g (lcompose h h) (/ m 2))))) (iter identity f n))

I personally would rather like to avoid using compose (as the only actual use I see in it would be in the logarithmic solution given above).

```
(define (repeated f n)
(define (repeated-step counter input)
(if (> counter n)
input
(f (repeated-step (+ counter 1) input))
)
)
(lambda (x) (repeated-step 1 x))
)
```

What do you guys think about this way of doing it? I believe it generates a linear iterative process:

```
(define (repeated f n)
(lambda (x)
(define (iter n result)
(cond ((= n 0) result)
((odd? n) (iter (- n 1) (f result)))
(else
(iter (- n 2) ((compose f f) result)))))
(iter n x)))
```

Is this another correct way of solving? I get the right answer when testing the given example from the book: ((repeated square 2) 5) = 625. I know I'm missing something. New to Scheme and this course, so feedback/criticisms welcomed. Could someone provide a good explanation of this?

```
(define (repeated f n)
(lambda (x) (f (f x))))
```

^That's not quite right, that just applies f twice. The goal is to apply f *n* times, as below:

(repeated f 1) ;; f(x) (repeated f 2) ;; f(f(x)) (repeated f 3) ;; f(f(f(x))) ...

As a hint, notice how your solution takes *n* as input and yet doesn't do anything with it in the body - that's a good indicator that something's off.

iterative solution using double with log(n) time complexity

```
(define (repeated2-iter f n)
(define (iter n current)
(cond ((= 1 n) current)
((even? n) (double (iter (/ n 2) current)))
(else (compose f (iter (- n 1) (compose f current))))
)
)
(iter n f)
)
```

My own solution, that does not use compose. Should be considered silly.

(define (repeated f n) (if (= n 1) (lambda (x) (f x)) (lambda (x) (f ((repeated f (- n 1)) x))))) ((repeated square 2) 5)

Using Racket `(require racket/trace)` we have no "chain of deferred operations".

It does something like the transform from `(compose f f)` to `(f f)` and it can be

alsodone for "the logarithmic solution". This is similar to "My own solution, that does not use compose. Should be considered silly.".Notice this is not logarithmic.

See other iterative implementation like "A logarithmic iterative solution." which is similar to exercise 1.16.

"iterative solution using double with log(n) time complexity" skips the `n=0` case where `(double f)` means `(compose f f)` and you assume `n>0` as the exercise says. But it is not iterative. Also `(compose f (iter (- n 1) (compose f current)))` has one redundant `compose`. It should be `(compose f (iter (- n 1) current))`. Then it is similar to "An solution with O(log n) complexity using compose:".