Week 7: Recursion

We are all familiar with recursion, wether we know it or not. Recursive structures are everywhere, from the food we eat, to a seashell. Recursion is the process of describing repeating items in a self-similar way (Wikipedia). Recursion frequently occurs in nature, and one example if a fern.

This fern, dubbed the Barnsley fern, is named the mathematician Michael Barnsley, who first discovered it. Each leaflet is a smaller version of the whole fern, and each sub-leaflet is a smaller version of the leaflet, and so on.

Recursion in Computer Science

In computer science there are certain problems that are best solved using a recursive solution. A recursive solution is one where the problem is reduced to a self-similar simpler form until a base case is reached.
For example, recursion is very useful when dealing with nested lists. If one wanted to sum up all the numbers in a nested list (ex. sum of [1,3,[1,[2,3]],5] = 15). The way most naturally think about this problem is recursive. We look at the list, and if its a number we add it to a sum, if the item is another list we add up all the items in that list, and add it to the sum. In this example the base case is when the item is a number. If the item of the list is another list, we reduce the problem to adding up the numbers in that sublist. However, if the item is a number we do not reduce the problem, we simply add it to the total.The way to write a method to do this in python is as follows.


This code constructs a list of integers using python comprehension, and takes the sum of the list. With the list [1,2,3] this function would create a list [1,2,3] and take the sum. If the list is nested, like [1,2,[3,4]] it would create a list [1,2, ... then it would take the sum of the nested list [3,4], and add it. The top list is now [1,2,7]. This is summed up for a final answer of 10.

Why use recursion?
Recursion can make solving some problems very easy. Often these problems deal with recursive data structures like nested lists, and is often simpler than a iterative solution. Some problems are very difficult to solve in a iterative fashion.

This code demonstrates the problem with solving a general case nested list. Unless one is sure of the depth of the list, an iterative solution is very difficult. Recursion can be difficult to understand at times, however it is an extremely powerful tool for solving problems.