Python lambdas implemented differently than standard functions?

Question

When trying to write an answer for another SO question, something really peculiar happened.

I basically came up with one gigabyte gcd and said it maybe slower because of recursion
gcd = lambda a,b : a if not b else gcd(b, a % b)

A simple test:

 assert gcd(10, 3) == 1 and gcd(21, 7) == 7 and gcd(100, 1000) == 100 

Here are a few steps:

 timeit.Timer('gcd(2**2048, 2**2048+123)', setup = 'from fractions import gcd').repeat(3, 100) # [0.0022919178009033203, 0.0016410350799560547, 0.0016489028930664062] timeit.Timer('gcd(2**2048, 2**2048+123)', setup = 'gcd = lambda a,b : a if not b else gcd(b, a % b)').repeat(3, 100) # [0.0020480155944824219, 0.0016460418701171875, 0.0014090538024902344] 

Well, I wonder what I expected a lot slower, but the timings are pretty close? perhaps importing a module is a problem ...

 >>> setup = ''' ... def gcd(a, b): ... """Calculate the Greatest Common Divisor of a and b. ... ... Unless b==0, the result will have the same sign as b (so that when ... b is divided by it, the result comes out positive). ... """ ... while b: ... a, b = b, a%b ... return a ... ''' >>> timeit.Timer('gcd(2**2048, 2**2048+123)', setup = setup).repeat(3, 100) [0.0015637874603271484, 0.0014810562133789062, 0.0014750957489013672] 

So far, quite close timings ok allows you to try larger values.

 timeit.Timer('gcd(2**9048, 2**248212)', setup = 'gcd = lambda a,b : a if not b else gcd(b, a % b)').repeat(3, 100) [2.866894006729126, 2.8396279811859131, 2.8353509902954102] [2.866894006729126, 2.8396279811859131, 2.8353509902954102] timeit.Timer('gcd(2**9048, 2**248212)', setup = setup).repeat(3, 100) [2.8533108234405518, 2.8411397933959961, 2.8430981636047363] 

Interesting, wondering what's going on?
I always assumed that recursion was slower due to the overhead of a function call, is lambdas an exception? and why didn’t I reach the limit of recursion?
If I use def , I will remove it immediately, if I increase the recursion depth by something like 10**9 , I really get a segmentation fault , probably a stack overflow ...

Update

 >>> setup = ''' ... import sys ... sys.setrecursionlimit(10**6) ... ... def gcd(a, b): ... return a if not b else gcd(b, a % b) ... ''' >>> >>> timeit.Timer('gcd(2**9048, 2**248212)', setup = 'gcd = lambda a,b:a if not b else gcd(b, a%b)').repeat(3, 100) [3.0647969245910645, 3.0081429481506348, 2.9654929637908936] >>> timeit.Timer('gcd(2**9048, 2**248212)', setup = 'from fractions import gcd').repeat(3, 100) [3.0753359794616699, 2.97499680519104, 3.0096950531005859] >>> timeit.Timer('gcd(2**9048, 2**248212)', setup = setup).repeat(3, 100) [3.0334799289703369, 2.9955930709838867, 2.9726388454437256] >>> 

even more mysterious ...

Answer 1

The type of lambda is exactly the same as the type of any other function, and in the case of both, if they are defined in another local area, the environment is captured.

The only difference is that functions defined using lambda syntax do not automatically become the value of a variable in the region in which it appears, and that lambda syntax requires the body to be one (possibly complex) expression, the value that is returned from the function .

As for the recursion speed - yes there is a small consignment note, but, apparently, not so much. The call overhead will mainly consist of the cost of allocating the stack frame.

Answer 2

 counter = 0 def gcd(a, b): global counter counter += 1 return a if not b else gcd(b, a % b) gcd(2**9048, 2**248212) print counter 

Seal 3 . Of course, there is no overhead for depth 3 recursion.