Decimal To Binary Python Getting an Extra Zero In Return String

Question

This is for a school project. I need to create a function using recursion to convert an integer to binary string. It must be a str returned, not an int. The base case is n==0, and then 0 would need to be returned. There must be a base case like this, but this is where I think I am getting the extra 0 from (I could be wrong). I am using Python 3.6 with the IDLE and the shell to execute it.

The function works just fine, expect for this additional zero that I need gone.

Here is my function, dtobr:

def dtobr(n):
    """
    (int) -> (str)
    This function has the parameter n, which is a non-negative integer, 
    and it will return the string of 0/1's
    which is the binary representation of n. No side effects. 
    Returns bianry string as mentioned. This is like the function
    dtob (decimal to bianary) but this is using recursion. 

    Examples:

    >>> dtob(27)
    '11011'
    >>> dtob(0)
    '0'
    >>> dtob(1)
    '1'
    >>> dtob(2)
    '10'
    """
    if n == 0:
        return str(0)
    return dtobr(n // 2) + str(n % 2)

This came from the function I already wrote which converted it just fine, but without recursion. For reference, I will include this code as well, but this is not what I need for this project, and there are no errors with this:

 def dtob(n):
    """
    (int) -> (str)

    This function has the parameter n, which is a non-negative integer, 
    and it will return the string of 0/1's
    which is the binary representation of n. No side effects. 
    Returns bianry string as mentioned.

    Examples:

    >>> dtob(27)
    '11011'
    >>> dtob(0)
    '0'
    >>> dtob(1)
    '1'
    >>> dtob(2)
    '10'
    """
    string = ""
    if n == 0:
        return str(0)
    while n > 0:
        remainder = n % 2
        string = str(remainder) + string
        n = n // 2

Hopefully someone can help me get ride of that additional left hand zero. Thanks!

A good way to debug something like this is to put a print statement inside your function. If you printed n in each iteration, you'd see that you're hitting the n==0 condition at the end every time. You need to change your conditional to account for the case when n==1. An easy thing is to do if n <= 1: return(str(n)) instead of the if n==0 check. — pault
– pault, Commented Feb 13, 2018 at 18:15

r.ook · Accepted Answer · 2018-02-13 19:17:35Z

1

You need to change the condition to recursively handle both the n // 2 and n % 2:

if n <= 1:
    return str(n)   # per @pault's suggestion, only needed str(n) instead of str(n % 2)
else:
    return dtobr(n // 2) + dtobr(n % 2)

Test case:

for i in [0, 1, 2, 27]:
    print(dtobr(i))

# 0
# 1
# 10
# 11011

FYI you can easily convert to binary format like so:

'{0:b}'.format(x)   # where x is your number

edited Feb 13, 2018 at 19:17

answered Feb 13, 2018 at 18:33

r.ook

13.9k2 gold badges26 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Alyssa Kelley Over a year ago

Thanks! I tried to give you a thumbs up, but I am not able to yet with my account, so here is a virtual thumbs up :D

r.ook Over a year ago

If you find this helpful, you can choose to accept the answer. It is by no means mandatory but can help highlight the answer helps resolves the issue for future visitors.

pault Over a year ago

Can simplify str(n%2) as it's equivalent to str(n) for n<=1

Ilija · Accepted Answer · 2018-02-13 18:51:12Z

Since there is already an answer that points and resolves the issue with recursive way, lets see some interesting ways to achieve same goal.

Lets define a generator that will give us iterative way of getting binary numbers.

def to_binary(n):
    if n == 0: yield "0"
    while n > 0:
        yield str(n % 2)
        n = n / 2

Then you can use this iterable to get decimal to binary conversion in multiple ways.

Example 1.

reduce function is used to concatenate chars received from to_binary iterable (generator).

from functools import reduce

def to_binary(n):
    if n == 0: yield "0"
    while n > 0:
        yield str(n % 2)
        n = n / 2

print reduce(lambda x, y: x+y, to_binary(0)) # 0
print reduce(lambda x, y: x+y, to_binary(15)) # 1111
print reduce(lambda x, y: x+y, to_binary(15)) # 11011

Example 2.

join takes iterable, unrolls it and joins them by ''

def to_binary(n):
    if n == 0: yield "0"
    while n > 0:
        yield str(n % 2)
        n = n / 2


print ''.join(to_binary(0)) # 0
print ''.join(to_binary(1)) # 1
print ''.join(to_binary(15)) # 1111
print ''.join(to_binary(27)) # 11011

Collectives™ on Stack Overflow

Decimal To Binary Python Getting an Extra Zero In Return String

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related