ISC Practicals and Theory - Decimal to Binary (Recursive Technique)

Converting a decimal number to binary means writing it in base 2, using only the digits 0 and 1. This note does it with recursion: the method rec_bin() calls itself with num / 2 and builds the binary number from the remainders, with no library shortcut.

Definition

To convert a decimal number to binary, divide it by 2 again and again, noting the remainder each time, until the quotient is 0. The remainders read from last to first are the binary digits.

For $10$:

• $10 \div 2$ gives quotient 5, remainder 0
• $5 \div 2$ gives quotient 2, remainder 1
• $2 \div 2$ gives quotient 1, remainder 0
• $1 \div 2$ gives quotient 0, remainder 1

Reading the remainders upwards: $10 = 1010_2$.

A recursive method calls itself. It needs a base case (where it stops) and a recursive case (a call on a smaller problem). Here the smaller problem is num / 2.

This program accepts whole numbers from 0 to 1023 only. A negative number, or a number above 1023, gets an error message. The largest accepted number, 1023, has 10 binary digits (1111111111), and the binary form is stored as a number made of those digits.

Algorithm

1. In main, create an object ob of class Binary. The constructor sets n and bin to 0.
2. Call input() to read the number into n.
3. If n is below 0 or above 1023, print an error message and stop.
4. Otherwise store rec_bin(n) in bin:
   • Base case: if num is 0, return 0.
   • Recursive case: return num % 2 + 10 * rec_bin(num / 2). The remainder num % 2 becomes the last digit, and the binary of num / 2 is shifted one place to the left by multiplying by 10.
5. Call display() to print the decimal number and its binary form.

The binary value is stored as a long made of the digits 0 and 1, so 10 is stored as the number 1010. For input 0 the base case returns 0 at once, so the output is 0.

Program

The class Binary has input() to read the number, rec_bin() to convert it recursively, and display() to print the result.

import java.util.Scanner;

/**
 * Class Binary converts a decimal number into binary using recursion.
 */
class Binary
{
    int n;      // stores the decimal number entered by the user
    long bin;   // stores the binary equivalent of n as a number of 0s and 1s

    /** Default constructor: sets both data members to 0. */
    Binary()
    {
        n = 0;
        bin = 0;
    }

    /** Accepts the decimal number from the user and stores it in n. */
    void input()
    {
        Scanner sc = new Scanner(System.in); // reads input from the keyboard
        System.out.print("Enter a decimal number (0 to 1023): ");
        n = sc.nextInt();
    }

    /**
     * Recursive method: finds the binary equivalent of num.
     * @param num the decimal number (0 or more)
     * @return the binary equivalent written as a long number, e.g. 10 gives 1010
     */
    long rec_bin(int num)
    {
        if (num == 0)                           // base case: nothing left to divide
            return 0;
        return num % 2 + 10 * rec_bin(num / 2); // remainder is the last binary digit; the rest comes from num / 2
    }

    /** Displays the decimal number and its binary equivalent. */
    void display()
    {
        System.out.println("Decimal = " + n);
        System.out.println("Binary  = " + bin);
    }

    /** main method: creates the object and calls the methods. */
    public static void main(String args[])
    {
        Binary ob = new Binary();   // object of class Binary
        ob.input();
        if (ob.n < 0 || ob.n > 1023)    // accepted range is 0 to 1023
            System.out.println("Invalid input: enter a number from 0 to 1023");
        else
        {
            ob.bin = ob.rec_bin(ob.n);
            ob.display();
        }
    }
}

Variable description table

Sample input and output

Enter a decimal number (0 to 1023): 10
Decimal = 10
Binary  = 1010

Enter a decimal number (0 to 1023): 0
Decimal = 0
Binary  = 0

Enter a decimal number (0 to 1023): 1023
Decimal = 1023
Binary  = 1111111111

Enter a decimal number (0 to 1023): 1024
Invalid input: enter a number from 0 to 1023

Dry run

Input: n = 10. The calls go down until num is 0; the values then return up, and each call adds its remainder to ten times the value returned from below.

Going down: rec_bin(10) calls rec_bin(5), which calls rec_bin(2), then rec_bin(1), then rec_bin(0).

Coming back up:

bin becomes 1010, and display() prints Binary = 1010, the same as the real run above.

Variations

1. Binary to decimal "Write a recursive method to convert a binary number to decimal."
2. Decimal to octal "Write a recursive method to convert a decimal number to octal."
3. Count of 1s "Write a program to count the number of 1s in the binary form of a number, using recursion."
4. Evil Number "A number is Evil if the count of 1s in its binary form is even. Write a program to check it using recursion."