# sicp-ex-1.43

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