Recursive function using lambda expression

Question

I need to create a recursive function repeat which takes in a function and uses the function n number of times with the value of x. Here's an iterative version that explains my issue a bit more in detail.

def repeat(fn, n, x):
    res = x
    for i in range(n):
        res = fn(res)
        print(res)
    return res

print(repeat(lambda x: x**2, 3, 3)) returns 6561

First it takes 3^2, then 3^2^2 which is 81 then again 3^2^2^2 = 6561. How can i make this recursive so it can work like this.

square_three_times = repeat(lambda x: x**2, 3)
print(square_three_times(3)) return 6561

I have tried something like this but im really lost and not sure what to do.

def repeat(fn, n):
    if n == 1:
        return fn(n):
    else:
        def result(x):
            return fn(n)
    return repeat(fn,result(x))

This obviously wouldnt work since the recursion would keep going forever. But im not sure how i should write this code since i first need to calculate 3^2 before taking the next step 9^2 and so on.

Do you need to make it recursive, or do you need it to work like that? Recursion doesn’t have to be involved. — Ry-
– Ry- ♦, Commented Dec 23, 2013 at 21:48
Why aren't you using the x parameter for your recursive variant? — filmor
– filmor, Commented Dec 23, 2013 at 21:49
If you want a function that only does the repetition implement repeat(fn, n, x) and use functools.partial to implement the currying. — filmor
– filmor, Commented Dec 23, 2013 at 21:52
Note that in Python 3.3 the given example in your question returns 81. — Lasse V. Karlsen
– Lasse V. Karlsen, Commented Dec 23, 2013 at 22:31

abarnert · Accepted Answer · 2013-12-23 21:52:20Z

4

First, you've got the base case wrong:

if n == 1:
    return fn

After all, repeat(fn, 1) is just a function that applies fn once—that's fn.

Now, if the base case is when n == 1, the recursive case is almost always going to be something where you pass n - 1 to yourself.

So, what's the difference between repeat(fn, n) and repeat(fn, n-1)? If you can't figure it out, expand a simple case out in your head or on paper:

repeat(fn, 3)(x): fn(fn(fn(x)))
repeat(fn, 2)(x): fn(fn(x))

And now it's obvious: repeat(fn, n) is the same thing as fn(repeat(fn, n-1)), right? So:

else:
    def new_fn(x):
        return fn(repeat(fn, n-1)(x))
    return new_fn

However, as filmor points out in the comments, it would be easier to use partial here:

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

def repeat(fn, n):
    return functools.partial(repeat3, fn, n)

answered Dec 23, 2013 at 21:52

abarnert

368k54 gold badges626 silver badges691 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Pierre Over a year ago

Thanks im trying to use your first example but i get invalid syntax on return fn, i edited my original post. EDIT: Never mind, found my silly misstake.

Eric · Accepted Answer · 2013-12-23 22:22:15Z

-1

You can define this very simply in terms of your old repeat function:

repeat_new = lambda fn, n: lambda x: repeat(fn, n, x)

square_three_times = repeat_new (lambda x: x**2, 3)
print(square_three_times(3))

answered Dec 23, 2013 at 22:22

Eric

98.1k54 gold badges257 silver badges389 bronze badges

3 Comments

abarnert Over a year ago

Yes, but that's not recursive, and the whole point of his question is how to do it recursively. (Plus, that's just a more verbose way of writing partial.)

Eric Over a year ago

@abarnert: functool.partial only gives you one level of partiality, doesn't it? Is there any easy way with partial to turn f(x, y, z) into g(x)(y)(z), instead of using g = lambda x: lambda y: lambda z: f(x, y, z)

abarnert Over a year ago

That's like saying that lambda only lets you write one level of partiality explicitly… You can always call partial on a partial.

Collectives™ on Stack Overflow

Recursive function using lambda expression

2 Answers 2

1 Comment

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related