# 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:

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