CODEWITHSUNDEEP
pythonpython-3.x
user2553807
user2553807

Reputation: 329

Python Decimal to Binary Recursive

I am writing a function that takes a parameter 'n' that will convert a decimal to a binary number using a recursive formula.

This is what I have for a non-recursive function but I need to figure out how to write it recursively. 

def dec2bin(n):
    bStr = ''
    if n < 0:
        return 'Must be a positive integer'
    elif n == 0:
        return '0'
    else:
        bStr += str(n%2)
    return bStr

Upvotes: 2

Views: 21437

Answers (5)

Abhishek Shah
Abhishek Shah

Reputation: 1

Modifying all the answers.

Solution 1

def dec2bin(num):
    if num == 0:
        return "" 
    else:
        return dec2bin(num//2) + str(num%2)

Call the function as:

dec2bin(233)

Solution 2

def dec2bin(num, result):
    if num == 0:
        return result 
    
    result = str(num % 2) + result
    return dec2bin(num//2, result)

Call the function as:

dec2bin(233, "")

Upvotes: 0

StickySli
StickySli

Reputation: 101

To improve rnbguy's answer, I've found that when your input is any number except 0, it does in fact return the binary representation with an additional '0' in the end.

To remove this the only solution I came up with is to add a global variable that remembers the previous value of the modulo n%2:

prev = 0
def dec2bin(n):
    global prev
    if n < 0:
        return 'Must be a positive integer'
    elif n == 0:
        if prev == 0:
            return '0'
        else:
            prev = 0
            return ''
    else:
        m = n%2
        prev = m
        return dec2bin(n//2) + str(m)

The reason behind this is when you try divmod(0, 2) the output is (0, 0), so we know the output must be a simple'0'. But if we have a number greater than 0, the recursive function will always end dividing 1//2 and 1%2 which will output the same as divmod(1, 2) == (0, 1).

To evade another '0' in the end of our output, we'll save the 1 of 1%2 in the global variable prev and check it when prev != 0 inside the second case since we currently have n = 0.

Before:

>>> print dec2bin(22)
010110
>>> print dec2bin(0)
0

After:

>>> print dec2bin(22)
10110
>>> print dec2bin(0)
0

Notice we have to add prev = 0 alongside return '' or else the print dec2bin(0) will output nothing since the last code executed set the prev to 1.

Upvotes: 1

cdlane
cdlane

Reputation: 41905

This is in follow up to @Stickysli's "improvement" on @rnbguy's solution. The issue being addressed was that of an unnecessary leading 0, but eliminating it in such a way as to not produce an empty result for zero itself. The proposed "improvement" is highly convoluted (more than twice the number of lines of code of the original) and relies on writing to a global variable!

I believe we can resolve the issue with fewer lines of code than the original by using a test to see if we're recursing on the number 1 or not, as that's the source of the problem:

def dec2bin(n):
    if n < 0:
        raise ValueError("Must be a positive integer")

    digit = str(n % 2)

    return dec2bin(n // 2) + digit if n > 1 else digit

After:

>>> dec2bin(22)
'10110'
>>> dec2bin(0)
'0'
>>>

Upvotes: 1

rnbguy
rnbguy

Reputation: 1399

Your code was almost okay. You don't really have to maintain bStr. Suppose you know the binary representation of n//2 then binary representation of n is binary representation of n//2 and 0 if n is evenly divisible by 2 or 1.

Like for n = 3. n//2 = 1. dec2bin(n//2) = '01' so dec2bin(n) = '01'+'1'[because 3 is not evenly divisible by 2] = '011'

Your code should be this.

def dec2bin(n):
    if n < 0:
        return 'Must be a positive integer'
    elif n == 0:
        return '0'
    else:
        return dec2bin(n//2) + str(n%2)

That's all.

Upvotes: 6

user2357112
user2357112

Reputation: 281594

Think about your base case. For what inputs would it make sense to just write the answer directly into your program? 0? 1? Probably not anything more than that; you don't want a giant elif chain going up to "okay, if it's 314, we can just return '100111010'". Think about how many numbers you need to hardcode the answer for, as a sort of foundation for the recursion, and which ones you can and should have the algorithm handle.

Think about your recursive call. If you want to produce a binary representation of n, what call to dec2bin would get you most of the answer, so you could then modify the result a bit and return that? Well, if n is bigger than 1, the binary representation of n is the binary representation of n//2 with another digit stuck onto the end, just like the decimal representation of n is the decimal representation of n//10 with another digit on the end.

Upvotes: 6

Related Questions