Recursion – Decimal to binary

Decimal integers can be converted to binary using successive divisions. For example, 57 becomes 111001 in binary.

57 ÷ 2 = 28 remainder 1
28 ÷ 2 = 14 remainder 0
14 ÷ 2 = 7 remainder 0
7 ÷ 2 = 3 remainder 1
3 ÷ 2 = 1 remainder 1
1 ÷ 2 = remainder 1

The binary representation of 57 is the binary representation of 28 (11100) followed by the remainder of 57÷2 (1). A recursive definition of the process can therefore be derived:

binary(57) = concat(binary(28),remainder(57/2))

The trick with this is that the last binary digit derived is actually the start of the binary number, as the digits are derived backwards. So it is important to incorporate this into the algorithm. Here is a C function to perform the conversion in a recursive manner:

int dec2bin(int n)
{
   if (n <= 0)
      return 0;
   else
      return 10 * dec2bin(n/2) + (n%2);
}

On entry to dec2bin(), the value of n is tested to see if it is zero. If n is greater than or equal to 1, then a recursive call is made to dec2bin() with n/2 as the argument (in C this will apply integer math). The value of dec2bin(n/2) is then multiplied by 10, and the remainder of n/2 (n%2), is added to it. This has the effect of concatenating the values. Here is the effect of the recursive calls shown as a visual trace:

An example, converting 57 to binary

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.