recursion - 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?

Answer 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!

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

Answer 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

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

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

Answer 6

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)

Answer 7

I have never used Python, but this is probably what you are looking for.

Answer 8

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.

Answer 9

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)

Answer 10

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.

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

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

No. (for most values of no).