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!
(written 2015-02-01, updated 2015-02-04)
Associated topics are indexed as below, or enter http://melksh.am/nnnn for individual articles
Q110 - Object Orientation and General technical topics - Programming Algorithms [202] Searching for numbers - (2005-02-04)
[227] Bellringing and Programming and Objects and Perl - (2005-02-25)
[642] How similar are two words - (2006-03-11)
[1157] Speed Networking - a great evening and how we arranged it - (2007-04-21)
[1187] Updating a page strictly every minute (PHP, Perl) - (2007-05-14)
[1391] Ordnance Survey Grid Reference to Latitude / Longitude - (2007-10-14)
[1840] Validating Credit Card Numbers - (2008-10-14)
[1949] Nuclear Physics comes to our web site - (2008-12-17)
[2189] Matching disparate referencing systems (MediaWiki, PHP, also Tcl) - (2009-05-19)
[2259] Grouping rows for a summary report - MySQL and PHP - (2009-06-27)
[2509] A life lesson from the accuracy of numbers in Excel and Lua - (2009-11-21)
[2586] And and Or illustrated by locks - (2010-01-17)
[2617] Comparing floating point numbers - a word of caution and a solution - (2010-02-01)
[2894] Sorting people by their names - (2010-07-29)
[2951] Lots of way of converting 3 letter month abbreviations to numbers - (2010-09-10)
[2993] Arrays v Lists - what is the difference, why use one or the other - (2010-10-10)
[3042] Least Common Ancestor - what is it, and a Least Common Ancestor algorithm implemented in Perl - (2010-11-11)
[3072] Finding elements common to many lists / arrays - (2010-11-26)
[3093] How many toilet rolls - hotel inventory and useage - (2010-12-18)
[3102] AND and OR operators - what is the difference between logical and bitwise varieties? - (2010-12-24)
[3451] Why would you want to use a Perl hash? - (2011-09-20)
[3620] Finding the total, average, minimum and maximum in a program - (2012-02-22)
[3662] Finding all the unique lines in a file, using Python or Perl - (2012-03-20)
[4325] Learning to program - what are algorithms and design patterns? - (2014-11-22)
[4401] Selecting RECENT and POPULAR news and trends for your web site users - (2015-01-19)
[4402] Finding sum, minimum, maximum and average in Python (and Ruby) - (2015-01-19)
[4652] Testing new algorithms in PHP - (2016-02-20)
[4656] Identifying the first and last records in a sequence - (2016-02-26)
[4707] Some gems from an introduction to Python - (2016-10-29)
Y112 - Python - Objects - Intermediate [296] Using a Python dictionary as a holder of object attributes - (2005-04-30)
[383] Overloading of operators on standard objects in Python - (2005-07-19)
[477] Class, static and unbound variables - (2005-10-25)
[656] Think about your design even if you don't use full UML - (2006-03-24)
[831] Comparison of Object Oriented Philosophy - Python, Java, C++, Perl - (2006-08-13)
[903] Pieces of Python - (2006-10-23)
[964] Practical polymorphism in action - (2006-12-04)
[1146] __new__ v __init__ - python constructor alternatives? - (2007-04-14)
[1217] What are factory and singleton classes? - (2007-06-04)
[1517] Python - formatting objects - (2008-01-24)
[1644] Using a utility method to construct objects of different types - Python - (2008-05-17)
[1661] Equality, sameness and identity - Python - (2008-05-31)
[1819] Calling base class constructors - (2008-10-03)
[2368] Python - fresh examples of all the fundamentals - (2009-08-20)
[2409] TypeError: super() argument 1 must be type, not classobj (Python) - (2009-09-18)
[2485] How do I set up a constant in Python? - (2009-10-31)
[2693] Methods that run on classes (static methods) in Python - (2010-03-25)
[2717] The Multiple Inheritance Conundrum, interfaces and mixins - (2010-04-11)
[2720] Multiple inheritance in Python - complete working example - (2010-04-14)
[2722] Mixins example in Python - (2010-04-14)
[2764] Python decorators - your own, staticmethod and classmethod - (2010-05-14)
[2785] The Light bulb moment when people see how Object Orientation works in real use - (2010-05-28)
[2889] Should Python classes each be in their own file? - (2010-07-27)
[2905] Defining static methods in Python - (2010-08-05)
[2994] Python - some common questions answered in code examples - (2010-10-10)
[3002] A list of special method and attribute names in Python - (2010-10-17)
[3442] A demonstration of how many Python facilities work together - (2011-09-16)
[3472] Static variables in functions - and better ways using objects - (2011-10-10)
[3524] Metaclasses (Python) and Metatables (Lua) - (2011-11-17)
[3796] Backquote, backtic, str and repr in Python - conversion object to string - (2012-07-05)
[3887] Inheritance, Composition and Associated objects - when to use which - Python example - (2012-10-10)
[4028] Really Simple Class and Inheritance example in Python - (2013-03-04)
[4094] Python Properties - how and why - (2013-05-18)
[4344] Python base and inherited classes, test harness and unit testing - new examples - (2014-12-07)
[4356] Object factories in C++, Python, PHP and Perl - (2014-12-19)
[4366] Changing what operators do on objects - a comparison across different programming languages - (2014-12-26)
[4449] Spike solution, refactoring into encapsulated object methods - good design practise - (2015-03-05)
[4450] Deciding whether to use parameters, conditional statements or subclasses - (2015-03-05)
[4541] Setting up and tearing down with the Python with keyword - (2015-10-16)
[4649] Object and Static methods - what is the difference; example in Python 3 - (2016-02-17)
[4717] with in Python - examples of use, and of defining your own context - (2016-11-02)
[4718] Defining an object that is a modified standard type in Python - (2016-11-02)
[4719] Nesting decorators - (2016-11-02)
Y105 - Python - Functions, Modules and Packages [96] Variable Scope - (2004-10-22)
[105] Distance Learning - (2004-10-31)
[294] Python generator functions, lambdas, and iterators - (2005-04-28)
[303] Lambdas in Python - (2005-05-06)
[308] Call by name v call by value - (2005-05-11)
[340] Code and code maintainance efficiency - (2005-06-08)
[386] What is a callback? - (2005-07-22)
[418] Difference between import and from in Python - (2005-08-18)
[561] Python's Generator functions - (2006-01-11)
[668] Python - block insets help with documentation - (2006-04-04)
[745] Python modules. The distribution, The Cheese Shop and the Vaults of Parnassus. - (2006-06-05)
[749] Cottage industry or production line data handling methods - (2006-06-07)
[775] Do not duplicate your code - (2006-06-23)
[821] Dynamic functions and names - Python - (2006-08-03)
[900] Python - function v method - (2006-10-20)
[912] Recursion in Python - (2006-11-02)
[913] Python - A list of methods - (2006-11-03)
[949] Sludge off the mountain, and Python and PHP - (2006-11-27)
[959] It's the 1st, not the 1nd 1rd or 1th. - (2006-12-01)
[1134] Function / method parameters with * and ** in Python - (2007-04-04)
[1163] A better alternative to cutting and pasting code - (2007-04-26)
[1202] Returning multiple values from a function (Perl, PHP, Python) - (2007-05-24)
[1464] Python Script - easy examples of lots of basics - (2007-12-08)
[1784] Global - Tcl, PHP, Python - (2008-09-03)
[1790] Sharing variables with functions, but keeping them local too - Python - (2008-09-09)
[1869] Anonymous functions (lambdas) and map in Python - (2008-11-04)
[1870] What to do with a huge crop of apples - (2008-11-04)
[1871] Optional and named parameters in Python - (2008-11-05)
[1879] Dynamic code - Python - (2008-11-11)
[2011] Conversion of OSI grid references to Eastings and Northings - (2009-01-28)
[2439] Multiple returns from a function in Python - (2009-10-06)
[2440] Optional parameters to Python functions - (2009-10-07)
[2481] Sample code with errors in it on our web site - (2009-10-29)
[2506] Good example of recursion in Python - analyse an RSS feed - (2009-11-18)
[2520] Global and Enable - two misused words! - (2009-11-30)
[2718] Python - access to variables in the outer scope - (2010-04-12)
[2766] Optional and named parameters to Python functions/methods - (2010-05-15)
[2878] Program for reliability and efficiency - do not duplicate, but rather share and re-use - (2010-07-19)
[2929] Passing a variable number of parameters in to a function / method - (2010-08-20)
[2998] Using an exception to initialise a static variable in a Python function / method - (2010-10-13)
[3159] Returning multiple values from a function call in various languages - a comparison - (2011-02-06)
[3280] Passing parameters to Python functions - the options you have - (2011-05-07)
[3459] Catching the fishes first? - (2011-09-27)
[3464] Passing optional and named parameters to python methods - (2011-10-04)
[3474] Python Packages - groupings of modules. An introduction - (2011-10-11)
[3695] Functions are first class variables in Lua and Python - (2012-04-13)
[3766] Python timing - when to use a list, and when to use a generator - (2012-06-16)
[3852] Static variables in Python? - (2012-08-29)
[3885] Default local - a good choice by the author of Python - (2012-10-08)
[3931] Optional positional and named parameters in Python - (2012-11-23)
[3945] vargs in Python - how to call a method with unknown number of parameters - (2012-12-06)
[4029] Exception, Lambda, Generator, Slice, Dict - examples in one Python program - (2013-03-04)
[4161] Python varables - checking existance, and call by name or by value? - (2013-08-27)
[4212] Python functions - an introduction to how they work - (2013-11-16)
[4361] Multiple yields and no loops in a Python generator? - (2014-12-22)
[4407] Python - even named code blocks are objects - (2015-01-28)
[4441] Reading command line parameters in Python - (2015-02-23)
[4448] What is the difference between a function and a method? - (2015-03-04)
[4645] What are callbacks? Why use them? An example in Python - (2016-02-11)
[4662] Recursion in Python - the classic example - (2016-03-07)
[4722] Embedding more complex code into a named block - (2016-11-04)
[4724] From and Import in Python - where is the module loaded from? - (2016-11-06)
Some other Articles
Java - converting an integer to a fixed length stringBinomial Coefficient (Pascal Triangle) objects in JavaJava -making sure you have the right versionsLocation, location location. And a chance of a giggle!A good example of recursion - a real use in PythonSetting up and using a dict in Python - simple first exampleAdditional Python courses added to our scheduleFixing damaged MySQL tables - Error 1712 and Error 2013Backup procedures - via backup server