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?
-
3I'm tempted to tag this what-the-heck or you-dont-want-to-do-this. Why don't you just use a normal function?– phihagCommented Jan 26, 2009 at 22:48
-
6I 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.– dsimardCommented Jan 26, 2009 at 23:12
-
1Reduce 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.– John FouhyCommented Jan 26, 2009 at 23:34
-
1please don't use reduce. Reduce with a recursive function is crazy complex. It will take forever. I think it's O(n**3) or something– S.LottCommented Jan 27, 2009 at 0:21
-
1@S.Lott bummer. Is that a problem with the Python interpreter or something more fundamental that I don't understand yet?– dsimardCommented Jan 27, 2009 at 7:42
17 Answers
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!
-
2
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))
– jfsCommented Jan 27, 2009 at 12:39 -
3
-
2FWIW, 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)
. Commented Nov 1, 2010 at 19:52 -
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)
Commented Nov 26, 2013 at 14:25 -
1Can somebody state why doing a recursive anonymous function call is "not recommended" Commented Jun 8, 2014 at 8:36
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)
-
2Since 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)
thenv = 10
and finallya(a, v)
. The complex lambda is designed to accept itself as its first parameter (hence why I've renamed the argument tomyself
), which it uses to call itself recursively– FelipeCommented Sep 11, 2015 at 17:07 -
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– gruvwCommented Jan 16, 2022 at 15:53
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
-
19
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]
,
-
1I 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...– pdcCommented Jan 28, 2009 at 13:59
-
Funny thing is, your Fibonacci example is a great example of something more naturally done with a generator. :-)– pdcCommented Jan 28, 2009 at 13:59
-
-
1+1, that's only answer I can understand, excluding these saying it's impossible and the function must have name to call herself. Commented Oct 26, 2014 at 21:59
-
1Actually you can! I got help and we figured it out! :) See: stackoverflow.com/questions/70714874/…– TrueYCommented Jan 14, 2022 at 21:07
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)
-
10I don't know Python, but that looks terrible. There's really got to be a better way. Commented Jan 27, 2009 at 3:41
-
1nobody - 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. Commented Jan 27, 2009 at 22:11
-
23Yeah, +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". :-) Commented Jul 29, 2009 at 22:11
-
1I thought it was impossible to write obfuscated code in python. I have been proven wrong. Thank you my friend Commented Apr 26, 2014 at 1:41
-
@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/…– TrueYCommented Jan 14, 2022 at 21:42
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)
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.
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.
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)
-
2As 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.– chepnerCommented Dec 12, 2021 at 15:47
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)
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.
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))
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
-
2
-
@ruohola this is general solution for all languages, but example is written on js Commented Jan 17, 2022 at 9:53
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))
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
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).
-
6( > 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. Commented Jul 3, 2012 at 15:34