ISC Practicals and Theory - Reverse of a Number (Recursive Technique)

Reversing a number means writing its digits in the opposite order, so 1234 becomes 4321. This note solves it with recursion: the method rec_rev() calls itself, each call moving one digit from the number to the reverse, until no digits are left.

Definition

The reverse of a number is the number formed by writing its digits from the last to the first.

• $1234$ reversed is $4321$.
• $1200$ reversed is $0021$, which as a number is $21$ (leading zeros do not count).

A recursive method is one that 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 the number with its last digit removed, num / 10.

This program accepts 0 and positive numbers only. A negative number is rejected with an error message and no reverse is found. Zeros at the end of the number become leading zeros in the reverse and are lost, so 1200 gives 21.

Algorithm

1. In main, create an object ob of class Reverse. The constructor sets n and rev to 0.
2. Call input() to read the number into n.
3. If n is negative, print an error message and stop.
4. Otherwise call rec_rev(n):
   • Base case: if num is 0, return (no digits are left).
   • Recursive case: multiply rev by 10 and add the last digit num % 10; then call rec_rev(num / 10) to handle the remaining digits.
5. Call display() to print the original number and rev.

rev is a long because the reverse of a large int can be bigger than the largest int (for example, reversing 2147483647 gives 7463847412), and a long holds it without overflow.

Program

The class Reverse has input() to read the number, rec_rev() to reverse it recursively, and display() to print the result.

import java.util.Scanner;

/**
 * Class Reverse accepts a number and finds its reverse using recursion.
 */
class Reverse
{
    int n;      // stores the number entered by the user
    long rev;   // stores the reverse of the number, built digit by digit

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

    /** Accepts the 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 number: ");
        n = sc.nextInt();
    }

    /**
     * Recursive method: reverses the digits of num into the data member rev.
     * @param num the part of the number still to be processed
     */
    void rec_rev(int num)
    {
        if (num == 0)                    // base case: no digits left
            return;
        rev = rev * 10 + num % 10;       // append the last digit of num to rev
        rec_rev(num / 10);               // recursive case: drop the last digit
    }

    /** Displays the original number and its reverse. */
    void display()
    {
        System.out.println("Original number = " + n);
        System.out.println("Reverse number  = " + rev);
    }

    /** main method: creates the object and calls the methods. */
    public static void main(String args[])
    {
        Reverse ob = new Reverse(); // object of class Reverse
        ob.input();
        if (ob.n < 0)               // negative numbers are not accepted
            System.out.println("Invalid input: enter a number that is 0 or more");
        else
        {
            ob.rec_rev(ob.n);
            ob.display();
        }
    }
}

Variable description table

Sample input and output

Enter a number: 1234
Original number = 1234
Reverse number  = 4321

Enter a number: 1200
Original number = 1200
Reverse number  = 21

Enter a number: -45
Invalid input: enter a number that is 0 or more

Dry run

Input: n = 1200. rev starts at 0. The calls go down until num becomes 0. rec_rev() is a void method, so nothing is returned upwards: each call finishes in turn after the call below it ends, and the answer is already in rev.

The calls then end one by one, back to main, and display() prints Reverse number = 21, the same as the real run above.

Variations

1. Palindrome number "Write a program to check whether a number is a palindrome (equal to its reverse), using recursion."
2. Sum of digits "Write a recursive method to find the sum of the digits of a number."
3. Count of digits "Write a recursive method to count the digits of a number."
4. Reverse of a string "Write a recursive method to reverse a string."