Java Program to Find Reverse of a Number Using Recursion
Recursion is a process by which a function calls itself repeatedly till it falls under the base condition and our motive is achieved.
To solve any problem using recursion, we should simply follow the below steps:
- Step 1: Assume the smaller problem from the problem that is similar to the bigger/original problem.
- Step 2: Decide the answer to the smallest valid input or smallest invalid input which would act as our base condition.
- Step 3: Approach the solution and link the answer to the smaller problem given by the recursive function to find the answer to the bigger/original problem using it.
Example:
Input: 14689
Output: 98641
Input: 7654321
Output: 1234567
Approach 1:
- In this approach, we can simply print the unit digit of a number.
- And then call the recursive function for the number after removing this unit digit (number/10)
- And this process continues till the number is reduced to a single-digit number.
Example:
num = 82695
reverse(82695)
|
|__print(5)
reverse(8269)
|
|__print(9)
reverse(826)
|
|__print(6)
reverse(82)
|
|__print(2)
reverse(8)
|
|__print(8)
return
// Java program to reverse
// an integer recursively
class GFG {
// Recursive function to print
// the number in reversed form
public static void Reverse(int num)
{
// base condition to end recursive calls
if (num < 10) {
System.out.println(num);
return;
}
else {
// print the unit digit of the given number
System.out.print(num % 10);
// calling function for remaining number other
// than unit digit
Reverse(num / 10);
}
}
// driver code
public static void main(String args[])
{
// number to be reversed
int num = 98765;
System.out.print("Reversed Number: ");
// calling recursive function
// to print the number in
// reversed form
Reverse(num);
}
}
Time complexity: O(log10n) where n is given input number.
Auxiliary space: O(1)
Approach 2:
- In this approach, we can simply maintain a variable in which we can store the number reversed till now.
- We can do this by extracting a unit digit from the number and then adding this extracted integer into the reversed number.
- But the key factor here is that we have to multiply the reversed number by 10 before adding this extracted number to the reversed number.
Example:
num = 48291
ans = 0 -> variable to store reversed number
How this works:
reverse(num)
|
|__ temp = num % 10 -> extracting unit digit from number
ans = ans*10 + temp -> adding temp at unit position in reversed number
reverse(num/10) -> calling function for remaining number
Implementation:
reverse(48291)
|
|__ temp=1
ans= 0*10 + 1 --> ans=1
reverse(4829)
|
|__ temp=9
ans= 1*10 + 9 --> ans=19
reverse(482)
|
|__ temp= 2
ans= 19*10 +2 --> ans=192
reverse(48)
|
|__ temp=8
ans=192*10 + 8 --> ans=1928
reverse(4)
|
|__ temp=4
ans=1928*10 +4 --> ans=19284
reverse(0)
|
|__ return ans
// Java program to reverse an integer recursively
class GFG {
// Variable to store reversed
// number after every
// recursive call
static int ans = 0;
static int Reverse(int var)
{
// base condition to end the
// recursive calling of function
if (var == 0) {
// We have reversed the
// complete number and
// stored in ans variable
return ans;
}
if (var > 0) {
// temp variable to store the digit at unit
// place in the number
int temp = var % 10;
// Add this temp variable in the ans variable
// which stores the number reversed till now
ans = ans * 10 + temp;
// recursive calling of function to reverse the
// remaining number
Reverse(var / 10);
}
// returning final answer when the number is
// reversed completely
return ans;
}
public static void main(String[] args)
{
// Number to be reversed
int var = 98765;
// Variable to store reversed number returned by
// reverse function
int rev;
// Calling reverse function and storing the return
// value in rev variable
rev = Reverse(var);
// Printing the Reversed Number
System.out.println("Reversed number: " + rev);
}
}
Time complexity: O(logn) where n is input number to be reversed.
Auxiliary space: O(1)
Note: Java does not throw an exception when an overflow occurs so a problem of overflow might occur if the reversed number is greater than Integer.MAX_VALUE (2147483647) in method 2 but there will be no such problem in method 1.
Approach 3:
While using recursion we can look at the number of digits and using that we can concatenate the reversed numbers.
import java.io.*;
import java.lang.*;
class GFG {
public int reverseDigits(int number)
{
if (number < 10)
return number;
int remainder = number % 10;
int reversedNumber
= this.reverseDigits(number / 10);
int numberOfDigits = (int)Math.log10(number) + 1;
return remainder
* (int)Math.pow(10, numberOfDigits - 1)
+ reversedNumber;
}
public static void main(String[] args)
{
GFG obj = new GFG();
int reversedNumber1 = obj.reverseDigits(987);
int reversedNumber2 = obj.reverseDigits(144321);
System.out.println(reversedNumber1);
System.out.println(reversedNumber2);
}
}