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.
Input: 14689 Output: 98641 Input: 7654321 Output: 1234567
- 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.
num = 82695 reverse(82695) | |__print(5) reverse(8269) | |__print(9) reverse(826) | |__print(6) reverse(82) | |__print(2) reverse(8) | |__print(8) return
Reversed Number: 56789
- 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.
num = 48291 ans = 0 -> variable to store reversed number How this works: reverse(num) | |__ temp = num % 10 -> extracting unit digit from nnumber ans = ans*10 + temp -> adding temp at unit position in reversed number reverse(num/10) -> calling function for remaing 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
Reversed number: 56789
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.
Attention reader! Don’t stop learning now. Get hold of all the important Java Foundation and Collections concepts with the Fundamentals of Java and Java Collections Course at a student-friendly price and become industry ready.