Recursive function using lambda's, why does this not work?

Question

I have a function that does some calculation, g(x). I now want to write a function that calculates g(g(g(...g(x)))), where g is applied n times. I tried to do this using repeat_fn (see below), but this does not work.

According to Recursive function using lambda expression the solution is to use functools.partial. This does indeed work, but I do not understand how. Also, I do not understand why my approach doesn't work.

g = lambda x: 2*x

# Function that returns the fˆn map
def repeat_fn(f, n):
     if n == 1:
         return f
    else:
        return lambda y: f( repeat_fn(f(y), n-1) )


 def repeat_fn_base(fn, n, x):
    if n == 1:
        return fn(x)
    else:
        return fn(repeat_fn_base(fn, n-1, x))

def repeat_fn2(fn, n):
    return functools.partial(repeat_fn_base, fn, n)


j = repeat_fn2(g, 5)
print(type(j))
print(j(2))

k = repeat_fn(g, 5)
print(type(k))
print(k(2))

It appears repeat_fn is only called once when i use k = repeat_fn(g, 5), while I would expect it to be called five times. Apparently, the recursion doesn't start until I supply k with an argument. Also print(k(2)) gives the following error: TypeError: unsupported operand type(s) for *: 'int' and 'function'.

This surprised me, because e.g. h = g(g(x) works just fine.

Can anyone shed some light on this? Thanks!

Answer 1

With return lambda y: f( repeat_fn(f(y), n-1) ), you are calling repeat_fn with the f parameter being the result of f(y), i.e. not a function. Instead, you should pass just f and then apply the result of fn_repeat (a function) to f(y) (or vice versa).

def repeat_fn(f, n):
    if n == 1:
         return f
    else:
        return lambda y: repeat_fn(f, n-1)(f(y))

k = repeat_fn(lambda x: 2*x, 5)
print(k(2))  # 64