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

Converting a decimal number to binary means writing it in base 2, using only 0 and 1. This version is a class with a parameterised constructor, and its recursive method printBin(int n) prints the binary digits in the correct order by calling itself first and printing afterwards.

Definition

To convert a decimal number to binary, divide by 2 repeatedly, noting each remainder, until the quotient is 0; the remainders read from last to first are the binary digits. For example $13 \div 2 = 6$ remainder 1, $6 \div 2 = 3$ remainder 0, $3 \div 2 = 1$ remainder 1, $1 \div 2 = 0$ remainder 1, so $13 = 1101_2$.

The remainders come out last digit first, so recursion is used to print them in reverse: the deepest call prints first.

This program accepts whole numbers from 0 to 1023 only. A negative number, or a number above 1023, gets an error message. Unlike a method that builds the binary value as a number, printBin() does not store the binary form anywhere: it prints it digit by digit.

Algorithm

1. In main, read the number into x and create the object ob with the parameterised constructor DecBin(x), which stores it in num.
2. Call isValid(). It returns true when num is from 0 to 1023. If not, print an error message and stop.
3. Call display(), which prints the heading, calls printBin(num) and then ends the line.
4. printBin(n):
   • Recursive case: if n is greater than 1, call printBin(n / 2) first. This prints the higher binary digits.
   • After that call returns (or straight away when n is 0 or 1, the base case where no further call is made), print n % 2, the last binary digit of n.

Because the printing happens after the recursive call, the digits appear from the left. Input 0 prints a single 0.

Program

The class DecBin stores the number in the constructor, checks it in isValid(), prints its binary form with the recursive printBin(), and display() ties the output together.

import java.util.Scanner;

/**
 * Class DecBin converts a decimal number to binary by printing its digits
 * through recursion (no binary value is stored).
 */
class DecBin
{
    int num;    // the decimal number to be converted

    /**
     * Parameterised constructor.
     * @param n the decimal number entered by the user
     */
    DecBin(int n)
    {
        num = n;    // store the number
    }

    /**
     * Checks that the number is within the accepted range.
     * @return true if num is from 0 to 1023, otherwise false
     */
    boolean isValid()
    {
        return num >= 0 && num <= 1023;
    }

    /**
     * Recursive method: prints the binary digits of n from left to right.
     * @param n the decimal number (0 or more)
     */
    void printBin(int n)
    {
        if (n > 1)                  // recursive case: first print the binary of n / 2
            printBin(n / 2);
        System.out.print(n % 2);    // base case (n is 0 or 1) reaches here directly; otherwise prints on the way back
    }

    /** Prints the heading, calls printBin and ends the line. */
    void display()
    {
        System.out.print("Binary of " + num + " = ");
        printBin(num);
        System.out.println();
    }

    /** main method: reads the number, creates the object and calls the methods. */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);    // reads input from the keyboard
        System.out.print("Enter a decimal number (0 to 1023): ");
        int x = sc.nextInt();                   // number typed by the user
        DecBin ob = new DecBin(x);              // object of class DecBin
        if (ob.isValid())
            ob.display();
        else
            System.out.println("Invalid input: enter a number from 0 to 1023");
    }
}

Variable description table

Sample input and output

Enter a decimal number (0 to 1023): 13
Binary of 13 = 1101

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

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

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

Dry run

Input: num = 13. Going down, each call with n > 1 calls printBin(n / 2) before printing. Coming back up, each call prints n % 2.

Going down: printBin(13) calls printBin(6), which calls printBin(3), which calls printBin(1). Here n > 1 is false, so no further call is made.

Printing, from the deepest call upwards:

The program prints Binary of 13 = 1101, 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. 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."