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:
- Assume the smaller problem from the problem which is similar to the bigger/original problem.
- Decide the answer to the smallest valid input or smallest invalid input which would act as our base condition.
- Approach the solution and link the answer to the smaller problem given by 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
// Java program to reverse// an integer recursivelyclass 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); }} |
Output
Reversed Number: 56789
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
// Java program to reverse an integer recursivelyclass 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); }} |
Output
Reversed number: 56789
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.