CODEWITHSUNDEEP
pythonalgorithmrecursionbinary
Dan LEE
Dan LEE

Reputation: 103

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

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!

Upvotes: 10

Views: 13485

Answers (4)

Michael Hodel
Michael Hodel

Reputation: 3030

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

Upvotes: 1

lode
lode

Reputation: 564

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)

Upvotes: 4

Harish Shisode
Harish Shisode

Reputation: 819

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

Upvotes: 4

MBo
MBo

Reputation: 80287

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

Upvotes: 5

Related Questions