Python Program to Flatten Nested List Using Recursion

You can flatten a nested list in Python using recursion by defining a function that checks if an element is a list and then recursively flattens it, like def flatten(lst): return [item for sublist in lst for item in (flatten(sublist) if isinstance(sublist, list) else [sublist])].

Examples

Input[1, 2, 3]

Output[1, 2, 3]

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

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

Input[]

Output[]

How to Think About It

To flatten a nested list, think of it like opening boxes inside boxes. For each item, check if it is a list (a box). If yes, open it by calling the same process again. If not, keep the item as is. Collect all items in one single list without any nesting.

Algorithm

1

Take the input list.

2

Create an empty list to store results.

3

For each element in the input list:

4

Check if the element is a list.

5

If it is, call the flatten function on this element and add all results to the result list.

6

If not, add the element directly to the result list.

7

Return the result list.

Code

python

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

nested_list = [1, [2, 3], [4, [5, 6]], 7]
print(flatten(nested_list))

Output

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

Dry Run

Let's trace the list [1, [2, 3], [4, [5, 6]], 7] through the flatten function.

1

Start with the full list

lst = [1, [2, 3], [4, [5, 6]], 7], result = []

2

Process first item 1

1 is not a list, append 1 to result -> result = [1]

3

Process second item [2, 3]

[2, 3] is a list, call flatten([2, 3])

4

Flatten [2, 3]

Both 2 and 3 are not lists, return [2, 3]

5

Extend result with [2, 3]

result = [1, 2, 3]

6

Process third item [4, [5, 6]]

[4, [5, 6]] is a list, call flatten([4, [5, 6]])

7

Flatten [4, [5, 6]]

4 is not a list, append 4; [5, 6] is a list, call flatten([5, 6])

8

Flatten [5, 6]

5 and 6 are not lists, return [5, 6]

9

Combine results

return [4, 5, 6]

10

Extend main result

result = [1, 2, 3, 4, 5, 6]

11

Process last item 7

7 is not a list, append 7 -> result = [1, 2, 3, 4, 5, 6, 7]

12

Return final result

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

Step	Current Item	Is List?	Result List
1	1	No	[1]
2	[2, 3]	Yes	[1, 2, 3]
3	[4, [5, 6]]	Yes	[1, 2, 3, 4, 5, 6]
4	7	No	[1, 2, 3, 4, 5, 6, 7]

Why This Works

Step 1: Check if item is a list

The function uses isinstance(item, list) to decide if it needs to open a nested list or just add the item.

Step 2: Use recursion to flatten nested lists

If the item is a list, the function calls itself to flatten that smaller list before adding its items.

Step 3: Collect all items in one list

All non-list items and flattened sublist items are added to a single result list, removing all nesting.

Alternative Approaches

Using a generator with yield

python

def flatten_gen(lst):
    for item in lst:
        if isinstance(item, list):
            yield from flatten_gen(item)
        else:
            yield item

nested_list = [1, [2, 3], [4, [5, 6]], 7]
print(list(flatten_gen(nested_list)))

This method uses a generator to yield items one by one, which can be more memory efficient for large lists.

Using iterative approach with stack

python

def flatten_iter(lst):
    stack = lst[::-1]
    result = []
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            stack.extend(item[::-1])
        else:
            result.append(item)
    return result

nested_list = [1, [2, 3], [4, [5, 6]], 7]
print(flatten_iter(nested_list))

This avoids recursion by using a stack, which can prevent maximum recursion depth errors on very deep lists.

Complexity: O(n) time, O(n) space

Time Complexity

The function visits every element once, including all nested elements, so the time grows linearly with the total number of elements.

Space Complexity

The extra space is used for the result list and the recursion call stack, both proportional to the total number of elements.

Which Approach is Fastest?

The recursive and iterative methods have similar time complexity, but the iterative approach avoids recursion limits and may be faster for very deep lists.

Approach	Time	Space	Best For
Recursive	O(n)	O(n)	Simple code, moderate depth
Generator with yield	O(n)	O(n)	Memory efficient, lazy evaluation
Iterative with stack	O(n)	O(n)	Very deep or large nested lists