Repeated Function Application

Question

I'm having trouble with a question which follows: Write a recursive function repeatedlyApply that takes as arguments a function f of one argument and a positive integer n. The result of repeatedlyApply is a function of one argument that applies f to that argument n times.

So, for example, we would have

repeatedlyApply(lambda x: x+1,10)(100) ==> 110

You may assume that the following function has been defined. You don't have to use it, but it can contribute to a pretty solution.

def compose(f,g):
    return lambda x: f(g(x))

So far i've written this

def compose(f,g):
    return lambda x: f(g(x))

def recApply(f,n):
    for i in range(n):
        return recApply(compose(f,f), n-1)
    return f

I'm going wrong somewhere because using the above example recApply(lambda x: x+1,10)(100) i get 1124.

Help much appreciated

Answer 1

I have a solution based on lambdas:

>>> f = lambda x: x + 10
>>> iterate = lambda f, n, x : reduce(lambda x, y: f(x), range(n), x)
>>> iterate(f, 10, 3)
103
>>> iterate(f, 4, 4)
44
>>> f10 = lambda x: iterate(f, 10, x)
>>> f10(5)
105

Answer 2

Correct answer is:

def recApply(func, n):
    if n > 1:
        rec_func = recApply(func, n - 1)
        return lambda x: func(rec_func(x))
    return func

And the output:

>>>> print recApply(lambda x: x+1,10)(100)
110