4.10. Recursion (advanced)

[This section borrows an example from Paul Barry’s Head First Python] This section contains examples motivating an important computing concept: recursion:

>>> movies = ["The Holy Grail", 1975, "Terry Jones & Terry Gilliam", 91,
            ["Graham Chapman", ["Michael Palin", "John Cleese",
                    "Terry Gilliam", "Eric Idle", "Terry Jones"]]]

>>> print(movies)
['The Holy Grail', 1975, 'Terry Jones & Terry Gilliam', 91,
   ['Graham Chapman', ['Michael Palin', 'John Cleese', 'Terry Gilliam',
                        'Eric Idle', 'Terry Jones']]]

Printing the list is not very helpful. The elements of the list seem to arranged in a haphazard fashion and they are printed with quotes around them.

Suppose we want to print out each element of the movies list on its own line without the string quotes. This is what the print command does when applied to a string. The problem is that movies is a list. To print out the individual members of that list as desired, we need to administer the print command to each of the elements in turn, and that requires a loop:

>>>  for each_item in movies:
       print(each_item)
The Holy Grail
1975
Terry Jones & Terry Gilliam
91
['Graham Chapman',
  ['Michael Palin', 'John Cleese', 'Terry Gilliam',
  'Eric Idle', 'Terry Jones']]

This started to work. The first four elements printed out just fine. The problem is that the last element of the movie list is not a string but another list. That is, the nested structure is recursive: the structure reoccurs inside itself, a list inside a list, with the inner list having elements of its own. To print out the individual members of that inner list as desired, we need to administer the print command to each of the elements in turn, and that requires another loop.

movies = ["The Holy Grail", 1975, "Terry Jones & Terry Gilliam", 91, 
                ["Graham Chapman", ["Michael Palin", "John Cleese",
                        "Terry Gilliam", "Eric Idle", "Terry Jones"]]]


for each_item in movies:
    if isinstance(each_item, list):
        for nested_item in each_item:
            print(nested_item)
    else:
        print(each_item)

for each_item in movies:
	if isinstance(each_item, list):
	    for nested_item in each_item:
	        if isinstance(nested_item, list):
	            for deeper_item in nested_item:
		            print(deeper_item)
                else:
                    print(nested_item)
	else:
	    print(each_item)

There is still a problem…

movies = ["The Holy Grail", 1975, "Terry Jones & Terry Gilliam", 91, 
                ["Graham Chapman", ["Michael Palin", "John Cleese",
                        "Terry Gilliam", "Eric Idle", "Terry Jones"]]]


def print_lol(a_list):
    for each_item in a_list:
        if isinstance(each_item, list):
            print_lol(each_item)
        else:
            print(each_item)
            

print_lol(movies)

Summarizing what we learned

• We had a data structure with a nested structure:

The structure of our example list.

• We learned how to use for loops to go through the elements of a nested structure.

• This strategy has a limitation. If the structure is recursive, the basic problem isn’t solved. We are still administering the print command to lists and not to the elements inside them.

• To write a function that can descend through an arbitrary number levels of nesting, we need to use a recursive function, a function that calls itself whenever it encounters a list.

The idea of recursion is a powerful idea that has many computational applications, and this very simple example doesn’t really begin to scratch the surface.