On Wed, 2009-02-11 at 09:15 +0900, Li Chen wrote:

Hi all,

In order to study recursion, I want to change a decimal number into a

binary number based on the algorithm on website

http://www.trunix.org/programlama/cpp/fred/notes/cpp/misc/decimal2binary.html

But my codes don’t work. Any idea or optimization?

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…

Matt