In my previous post, we (all the math n00bs out there) learned the secrets of the Binary system. We came to understand the basic formula for taking a binary number and converting it to its Base-10 (human-friendly) counterpart.
To sum up:
- Take the digit at each index (indices start at 0 and count upwards from right to left)
- Multiply each digit by 2 to power of that index number
- Find the sum of each of those products
- Keep going until you run out of binary digits!
This step-by-step process (especially the "keep going until...") lends itself nicely to recursion.
Let's brush up on our recursive chops and write a simple Ruby method for converting any Binary number into a Base-10 number.
Step 1: Finding the Product for Each Index
Let's say we have the Binary number
100100101100
Our first step is to take the digit at the first index (remember we're going from right -> left here), i.e. the digit in the ten's place.
How do we grab the value at the ten's place of a given number?
By finding the remainder of that number divided by 10. The Ruby modulo, %, operator is what we want.
remainder = num % 10
Then, we want to take that number and multiply it by the value of 2 to the power of that index number.
product = remainder * (2**i)
Once we have calculated that product, we want to perform the same steps on the number at the next index.
Step 2: Calculating Each Successive Index Digit
We know we can grab the digit in the ten's place of a given number. If only we could make the number at the _next_index actually be the number in the ten's place.
If we divide our number by 10, we can do just that!
num /= 10
Once we've performed this calculation, we can simply repeat the steps above with our new number.
Step 3: Summing It Up
We need to ensure that the product of our calculations at each index gets added up to the product of our calculations at the previous index.
We can make this happen by adding the product of the current step to the return of recursively calling our method.
Let's put it all together:
def binary_translator(num, i=0)
product = num % 10 * 2**i
product + binary_translator(num/10, i+1)
end
But how will our method know when to stop traversing the indices?
Step 4: The Base Case
Earlier, we laid out that we want to stop calculating when we run out of binary digits. I.e. when we arrive at the last index of our binary number.
How will we know when this condition has been met?
We can winnow our binary number down, one digit at a time, by dividing it by 10.
For example:
100100101100 / 10 = 10010010110
Each time we divide the number by 10, it will lose the digit in it's ten's place.
By the time we arrive at the last remaining digit, the result of dividing that digit by 10 will always be zero.
For example:
1 / 10 = 0
So, we'll know we've arrived at the last digit when the result of dividing our number by 10 is zero. Let's update our method:
def binary_translator(num, i=0)
product = num % 10 * 2**i
return product if num < 1
product + binary_translator(num/10, i+1)
end
Here, we pass the result of dividing num by 10 into each recursive method call. We tell our method to return the current product and stop recursing, if num is less than 1. This will break us out of the recursive loop and cause the total sum of the products at each step of the recursion to be returned.
You can check out the code here!