Recursive definitions in Python

Question

I just run into the following way of implementing AutoVivification in Python:

from collections import defaultdict

Tree = lambda: defaultdict(Tree)

# common name by class, order, genus, and type-species
common_name = Tree()
common_name['Mammalia']['Primates']['Homo']['H. sapiens'] = 'human being'

How does the following construction work?

Tree = lambda: defaultdict(Tree)

Tree does not seem to be defined before the body of the lambda function, and it is not passed as an argument.

How does the body of the lambda function know of Tree before it is defined? What other types of recursive definitions are supported by the language?

it doesnt ... lambda's are executed when they are called ... — Joran Beasley
– Joran Beasley, Commented Jan 22, 2015 at 1:01

mgilson · Accepted Answer · 2015-01-22 01:01:22Z

4

That's the great thing about a dynamic language like python -- Tree is defined by the time you call it. It's no different than any other recursive function really ...

e.g. you probably wouldn't bat an eye to see this:

def recurse(i):
    if i > 0:
        recurse(i-1)

This works because python creates the recurse function. Then when you call it, python looks up the recurse function when it gets to that line and calls it and ...

In this case, it's really not much different -- Your lambda could be written (maybe more clearly) like this:

def Tree():
    return defaultdict(Tree)

answered Jan 22, 2015 at 1:01

mgilson

312k70 gold badges656 silver badges722 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

mgilson Over a year ago

Although, to be fair, you can implement recursive functions in much less dynamic languages as well -- You can even do it in a standardized way in C or Fortran (90)!

mgilson · Accepted Answer · 2015-01-22 01:03:40Z

2

It's the equivalent of:

def Tree():
    return defaultdict(Tree)

The contents of the function aren't evaluated immediately, only when it gets called, at which time it can know about Tree. This is the reason recursive functions can work at all.

edited Jan 22, 2015 at 1:03

mgilson

312k70 gold badges656 silver badges722 bronze badges

answered Jan 22, 2015 at 1:01

Eithos

2,49116 silver badges13 bronze badges

Collectives™ on Stack Overflow

Recursive definitions in Python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related