Repeat function python

Question

I'm stuck at higher-order functions in python. I need to write a repeat function repeat that applies the function f n times on a given argument x.

For example, repeat(f, 3, x) is f(f(f(x))).

This is what I have:

def repeat(f,n,x):
    if n==0:
        return f(x)
    else:
        return repeat(f,n-1,x)

When I try to assert the following line:

plus = lambda x,y: repeat(lambda z:z+1,x,y)
assert plus(2,2) == 4

It gives me an AssertionError. I read about How to repeat a function n times but I need to have it done in this way and I can't figure it out...

Answer 1

You have two problems:

1. You are recursing the wrong number of times (if n == 1, the function should be called once); and
2. You aren't calling f on the returned value from the recursive call, so the function is only ever applied once.

Try:

def repeat(f, n, x):
    if n == 1: # note 1, not 0
        return f(x)
    else:
        return f(repeat(f, n-1, x)) # call f with returned value

or, alternatively:

def repeat(f, n, x):
    if n == 0:
        return x # note x, not f(x)
    else:
        return f(repeat(f, n-1, x)) # call f with returned value

(thanks to @Kevin for the latter, which supports n == 0).

Example:

>>> repeat(lambda z: z + 1, 2, 2)
4
>>> assert repeat(lambda z: z * 2, 4, 3) == 3 * 2 * 2 * 2 * 2
>>> 

Answer 2

You've got a very simple error there, in the else block you are just passing x along without doing anything to it. Also you are applying x when n == 0, don't do that.

def repeat(f,n,x):
    """
    >>> repeat(lambda x: x+1, 2, 0)
    2
    """
    return repeat(f, n-1, f(x)) if n > 0 else x