Introduction

The clean recursive solution is to build the string one bit at a time and branch into two recursive calls at each step: one for 0 and one for 1. Since there are 2^n binary strings of length n, recursion maps naturally to the problem as a depth-first traversal of a binary decision tree.

A simple recursive generator

The most useful version is a generator because it yields results one by one instead of building the entire list in memory immediately:

1def generate_binary_strings(length: int, prefix: str = ""):
2    if length == 0:
3        yield prefix
4        return
5
6    yield from generate_binary_strings(length - 1, prefix + "0")
7    yield from generate_binary_strings(length - 1, prefix + "1")
8
9
10for value in generate_binary_strings(3):
11    print(value)

Output:

1000
2001
3010
4011
5100
6101
7110
8111

This works because each call reduces the remaining length by one. The base case is when no positions remain, at which point the current prefix is a complete binary string.

Why this recursive structure is a good fit

At every character position you have exactly two choices, so the recursion tree has two children per node. That makes the algorithm easy to reason about:

• Base case: no positions left, so emit the finished string.
• Recursive case: append 0, then append 1.

This direct structure is why recursion is such a natural teaching example here. You do not need extra index bookkeeping or nested loops that change with the target length.

If you want to collect the results into a list instead of streaming them, wrap the generator with list(...):

all_values = list(generate_binary_strings(4))
print(all_values)

Return a list directly if needed

If the caller definitely needs all results at once, you can write a list-returning recursive version:

1def binary_strings_list(length: int) -> list[str]:
2    if length == 0:
3        return [""]
4
5    smaller = binary_strings_list(length - 1)
6    return ["0" + value for value in smaller] + ["1" + value for value in smaller]
7
8
9print(binary_strings_list(3))

This version is still correct and readable. The generator version is often better for larger inputs because the total number of outputs grows exponentially, and you may not want all of them resident in memory at once.

Complexity and practical limits

No algorithm can avoid the fact that there are 2^n outputs. That means:

• Time complexity is O(n * 2^n) because you produce 2^n strings and each finished string has length n.
• Space usage for the generator call stack is O(n).
• Space usage for storing every result is O(n * 2^n).

This matters quickly. Length 5 gives 32 strings, which is trivial. Length 20 gives 1,048,576 strings, which is already large enough that you should think carefully before building a full list.

Variations on the same idea

You can also write the recursion by tracking the current position explicitly:

1def generate_with_buffer(length: int):
2    buffer = ["0"] * length
3
4    def backtrack(index: int):
5        if index == length:
6            yield "".join(buffer)
7            return
8
9        buffer[index] = "0"
10        yield from backtrack(index + 1)
11
12        buffer[index] = "1"
13        yield from backtrack(index + 1)
14
15    yield from backtrack(0)
16
17
18print(list(generate_with_buffer(3)))

This avoids repeated prefix concatenation and is a good pattern when the generated strings are longer or when you want a template for more advanced backtracking problems.

Common Pitfalls

The most common mistake is forgetting the base case or placing it at the wrong depth, which either causes infinite recursion or produces strings of the wrong length.

Another common issue is printing inside the recursive function when the caller actually needs the values returned. Yielding or returning results is more reusable than hard-coding output.

People also underestimate the size of the output. The recursion itself is fine for moderate n, but the total number of strings doubles with each added bit.

Finally, be careful with mutable shared state. If you use a buffer-based approach, always overwrite the current position before each recursive branch so one branch does not leak into the other.

Summary

• The best recursive solution branches on 0 and 1 at each position.
• A generator is often preferable because it streams results instead of storing everything at once.
• The base case is when the remaining length reaches zero.
• Output size grows as 2^n, so large n becomes expensive no matter how elegant the recursion is.
• A buffer-based backtracking version is a good optimization when repeated string concatenation becomes a concern.