I'm having trouble understanding the else statement in Python and how it's used in the context of flattening a list and working with recursion.
I came across this code snippet for flattening a list:
def flatten_list(lst):
if not isinstance(lst, list):
return [lst]
elif not lst:
return []
else:
return flatten_list(lst[0]) + flatten_list(lst[1:])
my_list = [1, 2, 3, [4, 5, 6], [7, 8, 9, [10, 11], 12], 13, 14]
print(flatten_list(my_list))
I tried running this code on PythonTutor to visualize the execution, but I'm still struggling to grasp how the algorithm works, particularly the recursive aspect. Could someone provide a clearer explanation or step-by-step breakdown of how this algorithm flattens a nested list using recursion? Thank you!
def flatten_list(lst):
How do you "flatten" an object? Well, it depends on what that object is.
if not isinstance(lst, list):
return [lst]
If the object is not a list, we assume it's already "flat". But we want to always return a list, so we wrap it in a list by itself (length 1) and return that.
By returning we stop execution and don't look at the next cases.
elif not lst:
return []
But if the object is a list, and it's empty (not lst), we return an empty list.
else:
Now comes the tricky part. The object is a list (otherwise it'd be caught by the first if), and it's not empty (otherwise it'd be caught by the elif). So we have to flatten an actual list of objects.
But hey, it's progress!
return flatten_list(lst[0]) + flatten_list(lst[1:])
Because we know the list is not empty, it'll always have a "first element". If the first element is a list, we'll flatten it, and if it's an object, we'll wrap it in a list. Either way it'll be flat.
Now, the rest of the list lst[1:] might or might not be empty. But that's ok, because flatten_list knows how to handle empty lists!
So we just repeat the process for the rest of the list, processing the first element of each "rest of list", until we process the whole list.
Think of the case [1, [2, 3]].
When you call flatten_list([1, [2, 3]]), you're passing a non-empty list, so the else branch will be executed. The recursion will then be:
flatten_list(1) + flatten_list([[2, 3]])
The first recursion calls flatten_list(1), which returns [1] (because of the elif branch). So now we have
[1] + flatten_list([[2, 3]])
Remember this statNow, flatten_list([[2, 3]]) is processing a list of lists. This list is not empty, so we execute the else branch again, which is equivalent to:
[1] + (flatten_list([2, 3]) + flatten_list([]))
Now we execute flatten_list([2, 3]), which is also non-empty, so our expression becomes:
[1] + ((flatten_list([2]) + flatten_list([3])) + flatten_list([]))
And we recurse again:
[1] + (((flatten_list(2) + flatten_list([])) + flatten_list([3])) + flatten_list([]))
This is looking complicated, but we're finally at simple cases: a non-list and and empty list. We know how to process those:
[1] + ((([2] + []) + flatten_list([3])) + flatten_list([]))
[1] + (([2] + flatten_list([3])) + flatten_list([]))
We now evaluate flatten_list([3]):
[1] + (([2] + (flatten_list(3) + flatten_list([]))) + flatten_list([]))
Which becomes:
[1] + (([2] + ([3] + [])) + flatten_list([]))
[1] + (([2] + [3]) + flatten_list([]))
[1] + ([2, 3] + flatten_list([]))
Finally, we have our last recursion call, on an empty list:
[1] + ([2, 3] + flatten_list([]))
[1] + ([2, 3] + [])
[1] + [2, 3]
[1, 2, 3]
Ta-da, a flat list!