Flattening Lists

Fully recursive solution

Consider this list:

[1, [2, 3], 4, [[5, 6], 7]] 

This list contains a mixture of integers and lists. These lists can also contain a mixture of integers and lists, and, in fact, the whole thing can be nested to any depth. You want to flatten this into a single list containing all the integers in the order they occur in the original unflattened list, as shown here:

[1, 2, 3, 4, 5, 6, 7] 

This is quite interesting because it is hard to come up with a solution that doesn’t involve recursion. But there are different degrees to which you can use recursion. We will start with a fully recursive solution.

A simple fully recursive solution works like this:

• We take the original list and divide it into two parts. The first element of the list is called the head, and the rest of the list will be called the tail.

• The basic method is to flatten the head and the tail and then join them together again.

• Since both parts of the list have been flattened, we get a fully flattened list when we join them together.

• We recursively call the flatten function to flatten the head and tail.

• We need the stopping conditions as well. If we are asked to flatten something that isn’t a list (for example if it is an integer), we create a list from the value and return that. And if we are asked to flatten an empty list, we return an empty list. Here is the code: