AI Hints
Home›DSA in Python Tutorial›Recursion Practice
DSA in Python · Lesson 45 of 132

Practice: Flatten a List

Lists inside lists.

⏱ 2 min read▶ Video at 52:08🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Here's a list with lists inside it, and more lists inside those. Turn it into one flat list of numbers. You don't know how deep it goes. Pause. Why is this perfect for recursion?

Practice: Flatten a List
From the video: Practice: Flatten a List
  • Lists inside lists
  • Unknown depth
  • Flatten it

Recursion handles any depth

For each item, if it's a list, we flatten it with the same function, and add all of its results. If it's a plain number, we add the number. The base case is hidden in there. A list with no inner lists simply never recurses. Run it. Every number, in order, however deep it was.

flatten.pypython
def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4]], [[5]], 6]))
Output
[1, 2, 3, 4, 5, 6]

Natural fits for recursion

Recursion shines when the data is shaped like itself. Folders contain folders. Lists contain lists. And trees contain smaller trees. For those, recursion is often the simplest code you can write. For a plain row of items, a loop is usually better.

keyvalue
Foldersinside folders
Nested listsinside lists
Treesmade of smaller trees
Plain rowsjust use a loop

Summary

When data is nested inside itself, recursion handles any depth naturally. Next, a new section. Searching, starting with binary search.

Key takeaways
  • Is it a list? Recurse
  • Otherwise, keep it
  • Any depth
Next up: Binary Search — halving a sorted list