A question was raised on comp.lang.ruby by Li Chen regarding recursion being used to convert decimals to binary. What follows is my response.
The main idea behind recursion is that we break a problem into a representation of the same problem. In this case, we are taking a number, n. We want the value of that n, modulo 2, + the binary value of (n / 2).
Using that approach, for 4, we’d get:
(n%2) + ((n/2)%2) + ((n/2)/2)%2
which is “001” — the reverse of what we were wanting. However, if we turn it around, we can say that the binary representation of n is equivalent to the binary representation of(n/2) + (n modulo 2).
Or, if you will:
def decimal_to_binary(num = 0)
((num > 1) ? decimal_to_binary(num / 2) : "") + (num % 2).to_s
end
No arrays needed, nor any reversing.
We could also have written it as:
def decimal_to_binary(num = 0)
if (num > 1) then
results = decimal_to_binary(num/2)
else
results = ""
end
results + (num % 2).to_s
end
So, were we to call it with 4, the following calls to decimal_to_binary would happen:
decimal_to_binary(4) (which returns the next line + "0") decimal_to_binary(2) (which returns the next line + "0") decimal_to_binary(1) (which returns "1")
or, if you will, “100”.
I’m sure there’s probably ways to optimize my code even more, but it works…..
