Repeated aplication of functions in Scheme?

Question

If f is a numerical function and n is a positive integer, then we can form the nth repeated application of f, which is defined to be the function whose value at x is f(f(...(f(x))...)). For example, if f is the function x + 1, then the nth repeated application of f is the function x + n. If f is the operation of squaring a number, then the nth repeated application of f is the function that raises its argument to the 2^nth 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 nth repeated application of f. Your procedure should be able to be used as follows:

((repeated square 2) 5) 625

You can use this to simplify the answer:

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

I know it's frowned upon when someone posts homework problems to be solved, but I really am stuck on this problem and it is due soon. Any help is appreciated. Thanks

Answer 1

Did you just delete and reask this question? I'm copying my former answer here (thankfully, my browser had cached it):

Well, you probably want something like this, right?

((repeated square 3) 5)
-> (square ((repeated square 2) 5))
-> (square (square ((repeated square 1) 5)))
-> (square (square (square ((repeated square 0) 5))))
-> (square (square (square (identity 5))))

(I don't know whether identity is predefined in Scheme. If not, it's easy to write.)

Now, this is not directly reproducible because you can't magically enclose code outside of the call to repeated with arbitrary stuff. However, what do these reduction steps look like when rewritten using compose? Can you make out a pattern in the resulting list of steps and reproduce it?

Answer 2

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