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

A binary number uses only the digits 0 and 1. Converting it to decimal means adding up each digit multiplied by the matching power of 2. This note does the conversion with a recursive method, toDecimal(), that calls itself on a shorter number each time, without Math.pow, Integer.parseInt or any other library shortcut.

Definition

In a binary number the rightmost digit has place value $2^0$, the next $2^1$, and so on. For example:

• $1101_2 = 1 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 13$
• $10110_2 = 16 + 0 + 4 + 2 + 0 = 22$

The recursive idea: the value of a binary number is its last digit plus 2 times the value of the remaining digits. So $1101_2 = 1 + 2 \times 110_2$, and $110_2 = 0 + 2 \times 11_2$, and so on. The remaining digits are obtained by n / 10 and the last digit by n % 10.

The binary number is typed with its digits together (for example 1101) and read as a long, so up to 19 binary digits are accepted and the decimal result always fits in an int. Input 0 is valid and gives 0. A negative number, or any number with a digit other than 0 or 1, is invalid.

Algorithm

1. In main, create an object ob of class BinToDec and call accept() to read the binary number into bin.
2. Call isBinary(bin). It returns false if the number is negative or any digit is other than 0 or 1.
   • If it returns false, print the "Invalid input" message and stop.
3. Otherwise call toDecimal(bin) and store the result in dec.
   • Base case: if n == 0, return 0.
   • Recursive case: return (int)(n % 10) + 2 * toDecimal(n / 10).
   • Each call works on a number with one digit less, so the calls must reach 0.
4. Call display() to print the decimal equivalent.

Program

accept() reads the number, isBinary() validates it, toDecimal() is the recursive method, and display() prints the answer.

import java.util.*;

/** class BinToDec: converts a binary number to its decimal equivalent using recursion. */
class BinToDec
{
    long bin;   // binary number entered by the user
    int dec;    // decimal equivalent of bin

    /** Default constructor: initialises the data members. */
    BinToDec()
    {
        bin = 0;
        dec = 0;
    }

    /** Reads the binary number from the user. */
    void accept()
    {
        Scanner sc = new Scanner(System.in);    // Scanner object for input
        System.out.print("Enter a binary number: ");
        bin = sc.nextLong();
    }

    /** Checks the number: returns true if it is not negative and every digit is 0 or 1.
        @param n the number to check
        @return true if n is a valid binary number, otherwise false */
    boolean isBinary(long n)
    {
        if (n < 0)
            return false;
        while (n > 0)                   // peel off the digits one by one
        {
            long d = n % 10;            // last digit of n
            if (d != 0 && d != 1)
                return false;           // a digit other than 0 or 1 found
            n = n / 10;                 // drop the last digit
        }
        return true;
    }

    /** Recursive method: converts a binary number to decimal.
        Base case: n == 0 gives 0.
        Recursive case: last digit + 2 * (value of the remaining digits).
        @param n binary number
        @return decimal value of n */
    int toDecimal(long n)
    {
        if (n == 0)
            return 0;                                   // base case
        return (int)(n % 10) + 2 * toDecimal(n / 10);   // recursive case
    }

    /** Displays the decimal equivalent. */
    void display()
    {
        System.out.println("Decimal equivalent = " + dec);
    }

    /** main: creates the object and calls the methods. */
    public static void main(String args[])
    {
        BinToDec ob = new BinToDec();   // object of the class
        ob.accept();
        if (ob.isBinary(ob.bin))
        {
            ob.dec = ob.toDecimal(ob.bin);
            ob.display();
        }
        else
            System.out.println("Invalid input: a binary number has only the digits 0 and 1");
    }
}

Variable description table

Sample input and output

Enter a binary number: 1101
Decimal equivalent = 13

Enter a binary number: 10110
Decimal equivalent = 22

Enter a binary number: 0
Decimal equivalent = 0

Enter a binary number: 1021
Invalid input: a binary number has only the digits 0 and 1

Dry run

Input 1101. The calls go down until n becomes 0, then the values come back up.

Calls going down

Values returning up

dec becomes 13, so the program prints Decimal equivalent = 13, the same as the real run above.

Variations

1. Decimal to Binary "Write a program to convert a decimal number to binary using a recursive method."
2. Binary to Decimal using a loop "Write a program to convert a binary number to decimal."
3. Decimal to Octal "Write a program to convert a decimal number to octal using a recursive method."