Can a lambda function call itself recursively in Python?

Question

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?

Solution 1

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!

Solution 2

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)

Solution 3

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

Solution 4

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],

Solution 5

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)

View more solutions

Comments

[Kyle Cronin]

I don't know Python, but that looks terrible. There's really got to be a better way.

[jfs]

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))

[Sakie]

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.

[pdc]

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...

[pdc]

Funny thing is, your Fibonacci example is a great example of something more naturally done with a generator. :-)

[Lennart Regebro]

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". :-)

[e-satis]

Useless and fun. That's why I love computing.

[martineau]

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) .

[new123456]

A much better answer than "No".

[Danny Milosavljevic]

( > 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.

[Juan Gallostra]

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)

[antimatter]

I thought it was impossible to write obfuscated code in python. I have been proven wrong. Thank you my friend

[ThorSummoner]

Can somebody state why doing a recursive anonymous function call is "not recommended"

[Eliza Weisman]

Nice job, you just turned Python into Lisp :)

[GingerPlusPlus]

+1, that's only answer I can understand, excluding these saying it's impossible and the function must have name to call herself.

[Felipe]

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 recursively

[bouteillebleu]

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.

[David]

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!

[7H3_H4CK3R]

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!

[Mateen Ulhaq]

Argh! Why does python have to have different behavior for lambda assignments in comparison to all other assignments!? And who uses recursive lambdas anyways?

[verbamour]

@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))

[ruohola]

The question was about Python.

[chepner]

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.

[TrueY]

Actually you can! I got help and we figured it out! :) See: stackoverflow.com/questions/70714874/…

[TrueY]

@habnabit 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: stackoverflow.com/questions/70714874/…

[gruvw]

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 readable

[gruvw]

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 readable

[giokoguashvili]

@ruohola this is general solution for all languages, but example is written on js

[Jason Hemann]

There are plenty of "poorman's Y" based solutions, in fact.