What is the best way to generate all binary strings of the given length in Python using Recursion?

user_14656274 0
Viewed 5386

I'm now studying recursion and try to build some codes to generate all binary strings of the given length 'n'. I found a code to use for loop:

n = 5
for i in range(2**n, 2**(n+1)):
    print(bin(i)[3:])

But is there any other way to solve this problem using recursion? Thank you!

recursion binary algorithm python
4 Answers

It's hard to determine what way is "the best" ;)

We have to add zero or one to current string and go to the next recursion level.

Stop-condition is reaching of needed length (here n-1 because we have to provide leading one corresponding to your example)

def genbin(n, bs = ''):
    if n-1:
        genbin(n-1, bs + '0')
        genbin(n-1, bs + '1')
    else:
        print('1' + bs)

genbin(4)

1000
1001
1010
1011
1100
1101
1110
1111
user_8444160

To elaborate on Harish and generate a list of strings

def generate_binary_strings(bit_count):
    binary_strings = []
    def genbin(n, bs=''):
        if len(bs) == n:
            binary_strings.append(bs)
        else:
            genbin(n, bs + '0')
            genbin(n, bs + '1')


    genbin(bit_count)
    return binary_strings

binary_strings = generate_binary_strings(6)
print(binary_strings)
user_11998090 
def getbin(n, s=['']):
    if n > 0:
        return [
            *getbin(n - 1, [i + '0' for i in s]),
            *getbin(n - 1, [j + '1' for j in s])
        ]
    return s
user_123637500

Answer given by MBo is not giving correct answer for input 2 and 3.

eg. Input: 2

Output should be:

0 0

0 1

1 0

1 1

Input: 3

Output should be:

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

I have modified same code as follows

def genbin(n, bs=''):
if len(bs) == n:
    print(bs)
else:
    genbin(n, bs + '0')
    genbin(n, bs + '1')


genbin(3)


000
001
010
011
100
101
110
111
user_124154660
Related