recursive lambda-expressions possible?

Question

I'm trying to write a lambda-expression that calls itself, but i can't seem to find any syntax for that, or even if it's possible.

Essentially what I wanted to transfer the following function into the following lambda expression: (I realize it's a silly application, it just adds, but I'm exploring what I can do with lambda-expressions in python)

def add(a, b):
   if a <= 0:
      return b
   else:
      return 1 + add(a - 1, b)

add = lambda a, b: [1 + add(a-1, b), b][a <= 0]

but calling the lambda form of add results in a runtime error because the maximum recursion depth is reached. Is it even possible to do this in python? Or am I just making some stupid mistake? Oh, I'm using python3.0, but I don't think that should matter?

Answer 1

Maybe you need a Y combinator?

Edit - make that a Z combinator (I hadn't realized that Y combinators are more for call-by-name)

Using the definition of the Z combinator from Wikipedia

>>> Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))

Using this, you can then define add as a completely anonymous function (ie. no reference to its name in its definition)

>>> add = Z(lambda f: lambda a, b: b if a <= 0 else 1 + f(a - 1, b))
>>> add(1, 1)
2
>>> add(1, 5)
6

Answer 2

Perhaps you should try the Z combinator, where this example is from:

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