Algorithm Design (4.7.1)

Recursion:

Using for.

>>> def factorial1(n):
...     result = 1
...     for i in range(n):
...             result *= (i + 1)
...     return result
... 
>>> factorial1(3)
6
>>> factorial1(8)
40320
>>> factorial1(10)
3628800

The same logic can be realized with recursion.

>>> def factorial2(n):
...     if n == 1:
...             return 1
...     else:
...             return n * factorial2(n-1)
... 
>>> factorial2(3)
6
>>> factorial2(8)
40320
>>> factorial2(10)
3628800
>>> 

The function itself is called inside of the function.

Using recursion in nltk.

>>> def size1(s):
...     return 1 + sum(size1(child) for child in s.hyponyms())
... 

Try with some examples.

>>> ws = nltk.corpus.wordnet.synset('planet.n.01')
>>> ws.hyponyms()
[Synset('outer_planet.n.01'), Synset('inferior_planet.n.01'), Synset('superior_planet.n.01'), Synset('jovian_planet.n.01'), Synset('morning_star.n.01'), Synset('terrestrial_planet.n.01')]
>>> size1(ws)
7

Maybe not a good example as there is no grand-children. Let's change to more abstract word.

>>> ws = nltk.corpus.wordnet.synset('animal.n.01')
>>> ws.hyponyms()
[Synset('herbivore.n.01'), Synset('work_animal.n.01'), Synset('omnivore.n.02'), Synset('pleurodont.n.01'), Synset('scavenger.n.03'), Synset('poikilotherm.n.01'), Synset('female.n.01'), Synset('critter.n.01'), Synset('molter.n.01'), Synset('pet.n.01'), Synset('domestic_animal.n.01'), Synset('survivor.n.03'), Synset('invertebrate.n.01'), Synset('hexapod.n.01'), Synset('pest.n.04'), Synset('mate.n.03'), Synset('marine_animal.n.01'), Synset('range_animal.n.01'), Synset('predator.n.02'), Synset('male.n.01'), Synset('adult.n.02'), Synset('metazoan.n.01'), Synset('racer.n.03'), Synset('mutant.n.02'), Synset('homeotherm.n.01'), Synset('acrodont.n.01'), Synset('darter.n.02'), Synset('varmint.n.02'), Synset('insectivore.n.02'), Synset('feeder.n.06'), Synset('biped.n.01'), Synset('thoroughbred.n.03'), Synset('prey.n.02'), Synset('peeper.n.03'), Synset('fictional_animal.n.01'), Synset('stayer.n.01'), Synset('larva.n.01'), Synset('captive.n.02'), Synset('game.n.04'), Synset('young.n.01'), Synset('creepy-crawly.n.01'), Synset('chordate.n.01'), Synset('zooplankton.n.01'), Synset('stunt.n.02'), Synset('migrator.n.02'), Synset('giant.n.01'), Synset('embryo.n.02')]
>>> size1(ws)
4357

The original synset('animal.n.01') has 47 hyponyms, however, the returned value of size1 is 4357. This means the function was called recursively.

If recursion is not used, the source code will be like following.

>>> def size2(s):
...     layer = [s]
...     total = 0
...     while layer:
...             total += len(layer)
...             layer = [h for c in layer for h in c.hyponyms()]
...     return total
... 
>>> size2(ws)
4357

This logic seems that put all synsets including children, grand-children and so on into "layer" then sum up the total number of synsets.

[code language="language="python'"]
>>> def insert(trie, key, value):
... if key:
... first, rest = key[0], key[1:]
... if first not in trie:
... trie[first] = {}
... insert(trie[first], rest, value)
... else:
... trie['value'] = value
...
>>> trie = nltk.defaultdict(dict)
>>> insert(trie, 'chat', 'cat')
>>> insert(trie, 'chien', 'dog')
>>> insert(trie, 'chair', 'flesh')
>>> insert(trie, 'chic', 'stylish')
>>> trie = dict(trie) # for nicer printing
>>> trie['c']['h']['a']['t']['value']
'cat'
>>> pprint.pprint(trie)
{'c': {'h': {'a': {'i': {'r': {'value': 'flesh'}}, 't': {'value': 'cat'}},
'i': {'c': {'value': 'stylish'}, 'e': {'n': {'value': 'dog'}}}}}}
|