Can a lambda function call itself recursively in Python?
Asked Answered
T

17

88

A regular function can contain a call to itself in its definition, no problem. I can't figure out how to do it with a lambda function though for the simple reason that the lambda function has no name to refer back to. Is there a way to do it? How?

Thence answered 26/1, 2009 at 22:42 Comment(6)
I'm tempted to tag this what-the-heck or you-dont-want-to-do-this. Why don't you just use a normal function?Periphery
I want to do is to run reduce() on an tree. The lambda works great on a 1-D list and recursion felt like a natural way to make it work on a tree. That said, the real reason is that I'm just learning Python, so I'm kicking the tires.Thence
Reduce works fine with named functions. Guido wanted to remove lambda expressions from the language for a while. They survived, but there's still no reason why you need to use them in any situation.Christenachristendom
please don't use reduce. Reduce with a recursive function is crazy complex. It will take forever. I think it's O(n**3) or somethingSebbie
@Sebbie bummer. Is that a problem with the Python interpreter or something more fundamental that I don't understand yet?Thence
@dsimard: reduce(f, (a,b,c,d)) is f(f(f(a, b), c), d).Byram
T
94

The only way I can think of to do this amounts to giving the function a name:

fact = lambda x: 1 if x == 0 else x * fact(x-1)

or alternately, for earlier versions of python:

fact = lambda x: x == 0 and 1 or x * fact(x-1)

Update: using the ideas from the other answers, I was able to wedge the factorial function into a single unnamed lambda:

>>> map(lambda n: (lambda f, *a: f(f, *a))(lambda rec, n: 1 if n == 0 else n*rec(rec, n-1), n), range(10))
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

So it's possible, but not really recommended!

Taxeme answered 26/1, 2009 at 23:4 Comment(10)
map(lambda n: (lambda f, n: f(f, n))(lambda f, n: n*f(f, n-1) if n > 0 else 1, n), range(10))Byram
Useless and fun. That's why I love computing.Detroit
FWIW, here's how to generate numbers in the Fibonacci series with the same technique (assigning it a name): fibonacci = lambda n: 0 if n == 0 else 1 if n == 1 else fibonacci(n-1)+fibonacci(n-2) .Wikiup
Another way of genreating Fibonacci numbers using lambdas and recusivity: f = lambda x: 1 if x in (1,2) else f(x-1)+f(x-2)Glare
Can somebody state why doing a recursive anonymous function call is "not recommended"Nadia
Because once your anonymous function is complex enough to need to be recursive, you might as well define it as a function using def rather than trying to keep it in a single-line lambda definition.Siblee
I'll add another sticking point to doing this: >>> fact = lambda x: 1 if x == 0 else x * fact(x-1) >>> fact_fun = fact >>> fact = 'Frogs are green' >>> fact_fun(10) Traceback (most recent call last): File "<input>", line 1, in <module> File "<input>", line 1, in <lambda> TypeError: 'str' object is not callable Which is really confusing since the lambda retains the scope from everything created after it!Muzz
Perhaps I am 9 years late on this but this has been the final step to proving that my conjecture is correct: every solvable problem can be put into a single python lambda and only said lambda. Useless and fun!Borowski
Argh! Why does python have to have different behavior for lambda assignments in comparison to all other assignments!? And who uses recursive lambdas anyways?Romaromagna
@martineau, doing this poster's wedging on your Fibonacci solution gives: map(lambda n: (lambda f, *a: f(f, *a))(lambda rec, n: 0 if n == 0 else 1 if n == 1 else rec(rec, n-1) + rec(rec, n-2), n), range(10))Bullard
C
66

without reduce, map, named lambdas or python internals:

(lambda a:lambda v:a(a,v))(lambda s,x:1 if x==0 else x*s(s,x-1))(10)
Charmian answered 2/1, 2012 at 16:34 Comment(2)
Since the first function and its return value are called immediately, they're only serving as assignments. Pythonized a bit, this code says a = lambda myself, x: 1 if x==0 else x * myself(myself, x-1) then v = 10 and finally a(a, v). The complex lambda is designed to accept itself as its first parameter (hence why I've renamed the argument to myself), which it uses to call itself recursivelyAbortifacient
I posted a new answer leveraging new python syntax := it gives (f:=lambda x: 1 if x == 0 else x*f(x - 1))(5) which is shorter and more readableCarinacarinate
M
38

Contrary to what sth said, you CAN directly do this.

(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f: (lambda i: 1 if (i == 0) else i * f(i - 1)))(n)

The first part is the fixed-point combinator Y that facilitates recursion in lambda calculus

Y = (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))

the second part is the factorial function fact defined recursively

fact = (lambda f: (lambda i: 1 if (i == 0) else i * f(i - 1)))

Y is applied to fact to form another lambda expression

F = Y(fact)

which is applied to the third part, n, which evaulates to the nth factorial

>>> n = 5
>>> F(n)
120

or equivalently

>>> (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f: (lambda i: 1 if (i == 0) else i * f(i - 1)))(5)
120

If however you prefer fibs to facts you can do that too using the same combinator

>>> (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f: (lambda i: f(i - 1) + f(i - 2) if i > 1 else 1))(5)
8
Mannequin answered 13/4, 2012 at 16:50 Comment(1)
Nice job, you just turned Python into Lisp :)Falgoust
B
23

You can't directly do it, because it has no name. But with a helper function like the Y-combinator Lemmy pointed to, you can create recursion by passing the function as a parameter to itself (as strange as that sounds):

# helper function
def recursive(f, *p, **kw):
   return f(f, *p, **kw)

def fib(n):
   # The rec parameter will be the lambda function itself
   return recursive((lambda rec, n: rec(rec, n-1) + rec(rec, n-2) if n>1 else 1), n)

# using map since we already started to do black functional programming magic
print map(fib, range(10))

This prints the first ten Fibonacci numbers: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55],

Bedclothes answered 26/1, 2009 at 23:16 Comment(6)
I think I finally understand what the Y combinator is for. But I think that in Python it would generally be easier to just use "def" and give the function a name...Bright
Funny thing is, your Fibonacci example is a great example of something more naturally done with a generator. :-)Bright
A much better answer than "No".Biestings
+1, that's only answer I can understand, excluding these saying it's impossible and the function must have name to call herself.Saponify
Actually you can! I got help and we figured it out! :) See: #70715374Ciprian
There are plenty of "poorman's Y" based solutions, in fact.Ousel
S
15

Yes. I have two ways to do it, and one was already covered. This is my preferred way.

(lambda v: (lambda n: n * __import__('types').FunctionType(
        __import__('inspect').stack()[0][0].f_code, 
        dict(__import__=__import__, dict=dict)
    )(n - 1) if n > 1 else 1)(v))(5)
Shush answered 27/1, 2009 at 2:52 Comment(5)
I don't know Python, but that looks terrible. There's really got to be a better way.Vuong
nobody - the point is that this looks horrible for a reason. Python isn't designed for it, and it's bad practice (in Python). Lambdas are limited by design.Minutia
Yeah, +1 for the worst Python code ever. When Perl people say "You can write maintainable code in Perl if you know what you are doing", I say "Yeah, and you can write unmaintainable code in Python if you know what you are doing". :-)Pili
I thought it was impossible to write obfuscated code in python. I have been proven wrong. Thank you my friendPhotopia
@Shush Thanks for the code! If I understood well, this code duplicates the lambda object, from the compiled code. IMHO finding the original object is a "better" way. See: #70715374Ciprian
H
8

This answer is pretty basic. It is a little simpler than Hugo Walter's answer:

>>> (lambda f: f(f))(lambda f, i=0: (i < 10)and f(f, i + 1)or i)
10
>>>

Hugo Walter's answer:

(lambda a:lambda v:a(a,v))(lambda s,x:1 if x==0 else x*s(s,x-1))(10)
Hydrogenize answered 27/3, 2016 at 20:53 Comment(0)
H
4
def recursive(def_fun):
    def wrapper(*p, **kw):
        fi = lambda *p, **kw: def_fun(fi, *p, **kw)
        return def_fun(fi, *p, **kw)

    return wrapper


factorial = recursive(lambda f, n: 1 if n < 2 else n * f(n - 1))
print(factorial(10))

fibonaci = recursive(lambda f, n: f(n - 1) + f(n - 2) if n > 1 else 1)
print(fibonaci(10))

Hope it would be helpful to someone.

Hemimorphite answered 24/3, 2018 at 20:43 Comment(0)
C
4

We can now use new python syntax to make it way shorter and easier to read:

Fibonacci:

>>> (f:=lambda x: 1 if x <= 1 else f(x - 1) + f(x - 2))(5)
8

Factorial:

>>> (f:=lambda x: 1 if x == 0 else x*f(x - 1))(5)
120

We use := to name the lambda: use the name directly in the lambda itself and call it right away as an anonymous function.

(see https://www.python.org/dev/peps/pep-0572)

Carinacarinate answered 16/1, 2022 at 15:51 Comment(0)
S
3

By the way, instead of slow calculation of Fibonacci:

f = lambda x: 1 if x in (1,2) else f(x-1)+f(x-2)

I suggest fast calculation of Fibonacci:

fib = lambda n, pp=1, pn=1, c=1: pp if c > n else fib(n, pn, pn+pp, c+1)

It works really fast.

Also here is factorial calculation:

fact = lambda n, p=1, c=1: p if c > n else fact(n, p*c, c+1)
Signore answered 8/9, 2019 at 13:8 Comment(1)
As long as you are speeding it up, don't use recursion at all. Linear recursion is better than a tree, but you'll still overflow the stack with a relatively small argument.Bannerman
H
1

I liked motokur's answer as its succint. Here's my thinking about finding the solution :

For recursion, we need to call the same method but since its a lambda, we can't get a ref to it. One way we can reference a name is via method parameters. So, the method we want to call should be passed as a parameter. ( Another way is to get a ref to the current method by inspecting the call stack as in habnabit's answer)

The next thing is to be able to pass different values to each recursive call. So we introduce another parameter to hold the value.

A example calculating the factorial of 6 :

(lambda f : f(f,6) )( lambda f, x : 1 if x <= 1 else x * f(f, x-1) )

OR

Defining the param from the start instead of hard-coding it :

(lambda f,x : f(f,x) )( (lambda f, x : 1 if x <= 1 else x * f(f, x-1)), 6)
Huesman answered 20/3, 2023 at 6:22 Comment(1)
Is that related to the Y combinator?Puerilism
B
0

Well, not exactly pure lambda recursion, but it's applicable in places, where you can only use lambdas, e.g. reduce, map and list comprehensions, or other lambdas. The trick is to benefit from list comprehension and Python's name scope. The following example traverses the dictionary by the given chain of keys.

>>> data = {'John': {'age': 33}, 'Kate': {'age': 32}}
>>> [fn(data, ['John', 'age']) for fn in [lambda d, keys: None if d is None or type(d) is not dict or len(keys) < 1 or keys[0] not in d else (d[keys[0]] if len(keys) == 1 else fn(d[keys[0]], keys[1:]))]][0]
33

The lambda reuses its name defined in the list comprehension expression (fn). The example is rather complicated, but it shows the concept.

Bantamweight answered 19/8, 2014 at 9:11 Comment(0)
H
0

Short answer

Z = lambda f : (lambda x : f(lambda v : x(x)(v)))(lambda x : f(lambda v : x(x)(v)))

fact = Z(lambda f : lambda n : 1 if n == 0 else n * f(n - 1))

print(fact(5))

Edited: 04/24/2022

Explanation

For this we can use Fixed-point combinators, specifically Z combinator, because it will work in strict languages, also called eager languages:

const Z = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))

Define fact function and modify it:

1. const fact n = n === 0 ? 1 : n * fact(n - 1)
2. const fact = n => n === 0 ? 1 : n * fact(n - 1)
3. const _fact = (fact => n => n === 0 ? 1 : n * fact(n - 1))

Notice that:

fact === Z(_fact)

And use it:

const Z = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)));

const _fact = f => n => n === 0 ? 1 : n * f(n - 1);
const fact = Z(_fact);

console.log(fact(5)); //120

See also: Fixed-point combinators in JavaScript: Memoizing recursive functions

Hem answered 8/3, 2018 at 18:14 Comment(2)
The question was about Python.Southern
@Southern this is general solution for all languages, but example is written on jsHem
I
0

I know this is an old thread, but it ranks high on some google search results :). With the arrival of python 3.8 you can use the walrus operator to implement a Y-combinator with less syntax!

fib = (lambda f: (rec := lambda args: f(rec, args)))\
      (lambda f, n: n if n <= 1 else f(n-2) + f(n-1))
Idolah answered 22/3, 2021 at 13:0 Comment(0)
A
0

I got some homework about it and figured out something, heres an example of a lambda function with recursive calls:

sucesor = lambda n,f,x: (f)(x) if n == 0 else sucesor(n-1,f,(f)(x)) 
Azeotrope answered 23/11, 2022 at 9:22 Comment(0)
A
-1

As simple as:

fac = lambda n: 1 if n <= 1 else n*fac(n-1)
Aftertaste answered 19/12, 2021 at 19:26 Comment(0)
R
-2

Lambda can easily replace recursive functions in Python:

For example, this basic compound_interest:

def interest(amount, rate, period):
    if period == 0: 
        return amount
    else:
        return interest(amount * rate, rate, period - 1)

can be replaced by:

lambda_interest = lambda a,r,p: a if p == 0 else lambda_interest(a * r, r, p - 1)

or for more visibility :

lambda_interest = lambda amount, rate, period: \
amount if period == 0 else \
lambda_interest(amount * rate, rate, period - 1)

USAGE:

print(interest(10000, 1.1, 3))
print(lambda_interest(10000, 1.1, 3))

Output:

13310.0
13310.0
Redden answered 13/6, 2019 at 12:5 Comment(0)
M
-3

If you were truly masochistic, you might be able to do it using C extensions, but this exceeds the capability of a lambda (unnamed, anonymous) functon.

No. (for most values of no).

Minutia answered 26/1, 2009 at 23:17 Comment(1)
( > this exceeds the capability of a lambda ) --- No, it doesn't. The Y combinator is like the most famous abstract construct there is and it does do that without any hacks.Cosmopolitan

© 2022 - 2024 — McMap. All rights reserved.