CODEWITHSUNDEEP
pythonalgorithm
Metadata
Metadata

Reputation: 2083

How to capture the first digit while converting a decimal number to binary digit using naive recursion?

I am trying to convert a decimal number to a binary digit in the below way using recursion.

def getbin(x: int, s: str):
    if int(x/2) > 0:
        y = int(x/2)
        s += str(y % 2)
        print(f'int(x/2): {int(x/2)}, y: {y}, st: {s}')
        getbin(y, s)
    elif int(x/2) == 1:
        s += '11'
        return s


if __name__ == '__main__':
    print(getbin(28, ''))

But when I call this, I can see in the output that the first digit of the binary number is not getting captured. I ran two test cases:

For the number 28, the expected output should be 00111 but the output is 0111: enter image description here

For the number 5, the output should be 101 but the output is 01 enter image description here

Could anyone let me know what is the mistake I am making here and how can I correct it ?

Upvotes: 0

Views: 122

Answers (1)

Nick
Nick

Reputation: 147216

Your problem is that you are testing against x/2 instead of testing against x. Thus you lose the most significant bit of the result. Try something like this:

def getbin(x: int, s: str):
    s += str(x % 2)
    y = x // 2
    if y > 0:
        return getbin(y, s)
    return s

Note also that you need to reverse the result of getbin to get the correct binary string.

Upvotes: 1

Related Questions