Binary to decimal using recursion

Question

I am trying to wrap my head around recursion. I need to convert a binary string of digits into a decimal value.

I've tried to switch around the actual recursion part of my code to no avail. Also, if anyone has seen any good videos or examples of recursion, classes, and inheritance please also link them. These last few concepts in my class have been difficult for me. Thank you.

The homework says the only function I need is the len() function.

def convertToDecimal(binNum):
    if len(binNum) < 1:
        return int(binNum)
    else:
        return int(binNum[0])*len(binNum)**2 #+ convertToDecimal(binNum[:-1])

bin = '11111111'
print(convertToDecimal(bin))

I feel like the commented out portion is on the right track but i still get errors.

What do you mean "with len() only", since you also use int, *, <, if, else, [:-1]... — trincot
– trincot, Commented Jul 25, 2019 at 17:36
You'll need a += 2 ** len(binNum) in there somewhere. Think about how you would convert binary to decimal without recurrsion... — Dan
– Dan, Commented Jul 25, 2019 at 17:39

trincot · Accepted Answer · 2019-07-25 18:23:05Z

4

Without **, int() and even without len(), but still with if, *, +, [:] (slicing), it could be done like this:

def convertToDecimal(binNum):
    if binNum == "0":
        return 0
    if binNum == "1":
        return 1
    return convertToDecimal(binNum[:-1])*2 + convertToDecimal(binNum[-1])

The first two if blocks represent the base case, i.e. they deal with the inputs that should not need another recursive call. In this case that is when the input is just one binary digit.

The other case is where recursion will be used: here we know the input has two or more characters. That "problem" is split into two parts: (1) the string that excludes the last binary digit and (2) the final character. These two separate "problems" are solved independently, and are then combined. The combination is made by multiplying the first result by 2. This is because we omitted the last digit, and in binary, such omission means we actually divided the binary number by 2. So that gets restored by the multiplication. The value for the final digit (the other recursive call) is then added to it.

Note how the first of the two calls makes the string one character shorter, and so we can be sure that after a while the stack of recursive calls will end with just one character. Then the base case will kick in, and while backtracking those intermediate results are multiplied by 2 (and again by 2, ...etc) making the powers of two for each binary bit.

edited Jul 25, 2019 at 18:23

answered Jul 25, 2019 at 17:44

trincot

357k38 gold badges282 silver badges338 bronze badges

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

2 Comments

Locke Over a year ago

Thank you so much. This makes sense to me. I still don't think i quite understand recursion in this case but I can definitely step through this code. I'm sorry for the confusion, the homework stated len() and int() could be used but nothing more advanced was necessary.

trincot Over a year ago

Added some explanations

StardustGogeta · Accepted Answer · 2019-07-25 17:47:48Z

1

def convertToDecimal(binNum):
    if len(binNum) < 1:
        return 0
    else:
        return (binNum[0] == "1") * 2 ** (len(binNum) - 1) + convertToDecimal(binNum[1:])

This seems to work for me. It evaluates the first digit, then adds the value of the rest of the string. When there is no more to add, it adds 0, then accumulates all the way up the chain to produce a final answer.

Personally, I prefer @trincot's answer because it doesn't use exponentiation.

answered Jul 25, 2019 at 17:47

StardustGogeta

3,3932 gold badges21 silver badges34 bronze badges

Comments

Andrej Kesely · Accepted Answer · 2019-07-25 17:57:53Z

0

One possible variation:

def convertToDecimal(*binNum, n=1):
    if not binNum:
        return 0
    return (int(binNum[-1])*n + convertToDecimal(*binNum[:-1], n=n*2))

print(convertToDecimal(*'11011'))

Prints:

answered Jul 25, 2019 at 17:57

Andrej Kesely

196k15 gold badges60 silver badges105 bronze badges

Collectives™ on Stack Overflow

Binary to decimal using recursion

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related