Python Decimal to Binary Recursive

Question

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

Answer 1

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.

Answer 2

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.