A good example of recursion - a real use in Python
Archive - Originally posted on "The Horse's Mouth" - 2015-02-01 13:56:28 - Graham Ellis
Recursion is where a named block of code calls itself. The "classic" demonstration is the code to generate a factorial number:
def factorial(n):
if n<2:
return n
else:
return n * factorial(n-1)
print factorial(10)
which is all very well as a demonstration, but as "best practice: it stinks. A simple loop would be a far better way to work out a factorial, being shorter, easier to follow, and much more robust where a large factorial could be called for.
There are good uses of recursion out there, but rarely in the sort of simple and straightforward programs we use while training, so it was a pleasure to come across one today in presenting some data for Lisa.
Scenario - a data file with some 20,000 records for individuals in Melksham, entered from censueses from the 19th and early 20th Century. And a requirement to relate the individuals covered to their parents, grandparents and great-grandparents (and so on). Sample program [here] and the data is [here].
It's very much a "spike solution" at the moment - much more to come in the form of graphic presentaton, navigation, etc - and I've been asked to write a descendants tree as well as an ancestor tree, which sets other challenges. However - to share - here's the sort of results thus far:
WomanWithCat:family grahamellis$ python tree.py Hannah Richards
0: 271676 Hannah Richards (1895 to )
1: 219102 Lewis Richards (1852 to )
2: 961927 Henry Richards (1821 to 1882 )
3: 838477 Samuel Richards (1780 to 1859 )
4: [away] Robert Richards (1746-)
4: [away] Nanny (Little) Richards
3: 986308 Ann N (Redman) Richards (1786 to 1866 )
4: 341447 Eli Redman (1760 to 1837 )
5: [away]
5: [away]
4: 174109 Ann Redman (1756 to 1854 )
5: [away]
5: [away]
2: 636549 Jane (Elliott) Richards (1827 to )
3: 876983 William Elliott (1802 to )
4: [away]
4: [away]
3: 544144 Sarah (Cleverley) Elliott (1809 to )
4: [away]
4: [away]
1: [away]
There are indeed two cases of recursion in this example - getParentTree builds up a nested set of triplets (two parents and self) as it navigates back up the generations, and parentPrint the displays the whole of the ancestorTree object that getParentTree has had a hand in creating.
Note also the generation number counter on the print routine which works out the inset of each name for pretty printing, and indeed keeps track - purely for display - of the generation number. Very much a "display of principle" example so far - much further to go. But it certainly shows the power of Python!