Home Accessibility Courses Twitter The Mouth Facebook Resources Site Map About Us Contact
A good example of recursion - a real use in Python

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
Y105 - Python - Functions, Modules and Packages
  [4724] From and Import in Python - where is the module loaded from? - (2016-11-06)
  [4722] Embedding more complex code into a named block - (2016-11-04)
  [4719] Nesting decorators - (2016-11-02)
  [4662] Recursion in Python - the classic example - (2016-03-07)
  [4645] What are callbacks? Why use them? An example in Python - (2016-02-11)
  [4448] What is the difference between a function and a method? - (2015-03-04)
  [4441] Reading command line parameters in Python - (2015-02-23)
  [4407] Python - even named code blocks are objects - (2015-01-28)
  [4361] Multiple yields and no loops in a Python generator? - (2014-12-22)
  [4212] Python functions - an introduction to how they work - (2013-11-16)
  [4161] Python varables - checking existance, and call by name or by value? - (2013-08-27)
  [4029] Exception, Lambda, Generator, Slice, Dict - examples in one Python program - (2013-03-04)
  [3945] vargs in Python - how to call a method with unknown number of parameters - (2012-12-06)
  [3931] Optional positional and named parameters in Python - (2012-11-23)
  [3885] Default local - a good choice by the author of Python - (2012-10-08)
  [3852] Static variables in Python? - (2012-08-29)
  [3766] Python timing - when to use a list, and when to use a generator - (2012-06-16)
  [3695] Functions are first class variables in Lua and Python - (2012-04-13)
  [3662] Finding all the unique lines in a file, using Python or Perl - (2012-03-20)
  [3474] Python Packages - groupings of modules. An introduction - (2011-10-11)
  [3472] Static variables in functions - and better ways using objects - (2011-10-10)
  [3464] Passing optional and named parameters to python methods - (2011-10-04)
  [3459] Catching the fishes first? - (2011-09-27)
  [3280] Passing parameters to Python functions - the options you have - (2011-05-07)
  [3159] Returning multiple values from a function call in various languages - a comparison - (2011-02-06)
  [2998] Using an exception to initialise a static variable in a Python function / method - (2010-10-13)
  [2994] Python - some common questions answered in code examples - (2010-10-10)
  [2929] Passing a variable number of parameters in to a function / method - (2010-08-20)
  [2878] Program for reliability and efficiency - do not duplicate, but rather share and re-use - (2010-07-19)
  [2766] Optional and named parameters to Python functions/methods - (2010-05-15)
  [2718] Python - access to variables in the outer scope - (2010-04-12)
  [2520] Global and Enable - two misused words! - (2009-11-30)
  [2506] Good example of recursion in Python - analyse an RSS feed - (2009-11-18)
  [2481] Sample code with errors in it on our web site - (2009-10-29)
  [2440] Optional parameters to Python functions - (2009-10-07)
  [2439] Multiple returns from a function in Python - (2009-10-06)
  [2011] Conversion of OSI grid references to Eastings and Northings - (2009-01-28)
  [1879] Dynamic code - Python - (2008-11-11)
  [1871] Optional and named parameters in Python - (2008-11-05)
  [1870] What to do with a huge crop of apples - (2008-11-04)
  [1869] Anonymous functions (lambdas) and map in Python - (2008-11-04)
  [1790] Sharing variables with functions, but keeping them local too - Python - (2008-09-09)
  [1784] Global - Tcl, PHP, Python - (2008-09-03)
  [1464] Python Script - easy examples of lots of basics - (2007-12-08)
  [1202] Returning multiple values from a function (Perl, PHP, Python) - (2007-05-24)
  [1163] A better alternative to cutting and pasting code - (2007-04-26)
  [1134] Function / method parameters with * and ** in Python - (2007-04-04)
  [959] It's the 1st, not the 1nd 1rd or 1th. - (2006-12-01)
  [949] Sludge off the mountain, and Python and PHP - (2006-11-27)
  [913] Python - A list of methods - (2006-11-03)
  [912] Recursion in Python - (2006-11-02)
  [900] Python - function v method - (2006-10-20)
  [821] Dynamic functions and names - Python - (2006-08-03)
  [775] Do not duplicate your code - (2006-06-23)
  [749] Cottage industry or production line data handling methods - (2006-06-07)
  [745] Python modules. The distribution, The Cheese Shop and the Vaults of Parnassus. - (2006-06-05)
  [668] Python - block insets help with documentation - (2006-04-04)
  [561] Python's Generator functions - (2006-01-11)
  [418] Difference between import and from in Python - (2005-08-18)
  [386] What is a callback? - (2005-07-22)
  [340] Code and code maintainance efficiency - (2005-06-08)
  [308] Call by name v call by value - (2005-05-11)
  [303] Lambdas in Python - (2005-05-06)
  [294] Python generator functions, lambdas, and iterators - (2005-04-28)
  [105] Distance Learning - (2004-10-31)
  [96] Variable Scope - (2004-10-22)

Y112 - Python - Objects - Intermediate
  [4718] Defining an object that is a modified standard type in Python - (2016-11-02)
  [4717] with in Python - examples of use, and of defining your own context - (2016-11-02)
  [4649] Object and Static methods - what is the difference; example in Python 3 - (2016-02-17)
  [4541] Setting up and tearing down with the Python with keyword - (2015-10-16)
  [4450] Deciding whether to use parameters, conditional statements or subclasses - (2015-03-05)
  [4449] Spike solution, refactoring into encapsulated object methods - good design practise - (2015-03-05)
  [4366] Changing what operators do on objects - a comparison across different programming languages - (2014-12-26)
  [4356] Object factories in C++, Python, PHP and Perl - (2014-12-19)
  [4344] Python base and inherited classes, test harness and unit testing - new examples - (2014-12-07)
  [4094] Python Properties - how and why - (2013-05-18)
  [4028] Really Simple Class and Inheritance example in Python - (2013-03-04)
  [3887] Inheritance, Composition and Associated objects - when to use which - Python example - (2012-10-10)
  [3796] Backquote, backtic, str and repr in Python - conversion object to string - (2012-07-05)
  [3524] Metaclasses (Python) and Metatables (Lua) - (2011-11-17)
  [3442] A demonstration of how many Python facilities work together - (2011-09-16)
  [3002] A list of special method and attribute names in Python - (2010-10-17)
  [2905] Defining static methods in Python - (2010-08-05)
  [2889] Should Python classes each be in their own file? - (2010-07-27)
  [2785] The Light bulb moment when people see how Object Orientation works in real use - (2010-05-28)
  [2764] Python decorators - your own, staticmethod and classmethod - (2010-05-14)
  [2722] Mixins example in Python - (2010-04-14)
  [2720] Multiple inheritance in Python - complete working example - (2010-04-14)
  [2717] The Multiple Inheritance Conundrum, interfaces and mixins - (2010-04-11)
  [2693] Methods that run on classes (static methods) in Python - (2010-03-25)
  [2485] How do I set up a constant in Python? - (2009-10-31)
  [2409] TypeError: super() argument 1 must be type, not classobj (Python) - (2009-09-18)
  [2368] Python - fresh examples of all the fundamentals - (2009-08-20)
  [1819] Calling base class constructors - (2008-10-03)
  [1661] Equality, sameness and identity - Python - (2008-05-31)
  [1644] Using a utility method to construct objects of different types - Python - (2008-05-17)
  [1517] Python - formatting objects - (2008-01-24)
  [1217] What are factory and singleton classes? - (2007-06-04)
  [1146] __new__ v __init__ - python constructor alternatives? - (2007-04-14)
  [964] Practical polymorphism in action - (2006-12-04)
  [903] Pieces of Python - (2006-10-23)
  [831] Comparison of Object Oriented Philosophy - Python, Java, C++, Perl - (2006-08-13)
  [656] Think about your design even if you don't use full UML - (2006-03-24)
  [477] Class, static and unbound variables - (2005-10-25)
  [383] Overloading of operators on standard objects in Python - (2005-07-19)
  [296] Using a Python dictionary as a holder of object attributes - (2005-04-30)

Q110 - Object Orientation and General technical topics - Programming Algorithms
  [4707] Some gems from an introduction to Python - (2016-10-29)
  [4656] Identifying the first and last records in a sequence - (2016-02-26)
  [4652] Testing new algorithms in PHP - (2016-02-20)
  [4402] Finding sum, minimum, maximum and average in Python (and Ruby) - (2015-01-19)
  [4401] Selecting RECENT and POPULAR news and trends for your web site users - (2015-01-19)
  [4325] Learning to program - what are algorithms and design patterns? - (2014-11-22)
  [3620] Finding the total, average, minimum and maximum in a program - (2012-02-22)
  [3451] Why would you want to use a Perl hash? - (2011-09-20)
  [3102] AND and OR operators - what is the difference between logical and bitwise varieties? - (2010-12-24)
  [3093] How many toilet rolls - hotel inventory and useage - (2010-12-18)
  [3072] Finding elements common to many lists / arrays - (2010-11-26)
  [3042] Least Common Ancestor - what is it, and a Least Common Ancestor algorithm implemented in Perl - (2010-11-11)
  [2993] Arrays v Lists - what is the difference, why use one or the other - (2010-10-10)
  [2951] Lots of way of converting 3 letter month abbreviations to numbers - (2010-09-10)
  [2894] Sorting people by their names - (2010-07-29)
  [2617] Comparing floating point numbers - a word of caution and a solution - (2010-02-01)
  [2586] And and Or illustrated by locks - (2010-01-17)
  [2509] A life lesson from the accuracy of numbers in Excel and Lua - (2009-11-21)
  [2259] Grouping rows for a summary report - MySQL and PHP - (2009-06-27)
  [2189] Matching disparate referencing systems (MediaWiki, PHP, also Tcl) - (2009-05-19)
  [1949] Nuclear Physics comes to our web site - (2008-12-17)
  [1840] Validating Credit Card Numbers - (2008-10-14)
  [1391] Ordnance Survey Grid Reference to Latitude / Longitude - (2007-10-14)
  [1187] Updating a page strictly every minute (PHP, Perl) - (2007-05-14)
  [1157] Speed Networking - a great evening and how we arranged it - (2007-04-21)
  [642] How similar are two words - (2006-03-11)
  [227] Bellringing and Programming and Objects and Perl - (2005-02-25)
  [202] Searching for numbers - (2005-02-04)


Back to
Setting up and using a dict in Python - simple first example
Previous and next
or
Horse's mouth home
Forward to
Location, location location. And a chance of a giggle!
Some other Articles
Java - converting an integer to a fixed length string
Binomial Coefficient (Pascal Triangle) objects in Java
Java -making sure you have the right versions
Location, location location. And a chance of a giggle!
A good example of recursion - a real use in Python
Setting up and using a dict in Python - simple first example
Additional Python courses added to our schedule
Fixing damaged MySQL tables - Error 1712 and Error 2013
Backup procedures - via backup server
4749 posts, page by page
Link to page ... 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95 at 50 posts per page


This is a page archived from The Horse's Mouth at http://www.wellho.net/horse/ - the diary and writings of Graham Ellis. Every attempt was made to provide current information at the time the page was written, but things do move forward in our business - new software releases, price changes, new techniques. Please check back via our main site for current courses, prices, versions, etc - any mention of a price in "The Horse's Mouth" cannot be taken as an offer to supply at that price.

Link to Ezine home page (for reading).
Link to Blogging home page (to add comments).

You can Add a comment or ranking to this page

© WELL HOUSE CONSULTANTS LTD., 2017: 404 The Spa • Melksham, Wiltshire • United Kingdom • SN12 6QL
PH: 01144 1225 708225 • EMAIL: info@wellho.net • WEB: http://www.wellho.net • SKYPE: wellho

PAGE: http://www.wellho.net/mouth/4410_A-g ... ython.html • PAGE BUILT: Sat May 27 16:49:10 2017 • BUILD SYSTEM: WomanWithCat