Posted on by Kalkicode
Code Recursion

Reverse a number using recursion

In this article, we will explore the concept of reversing a number using recursion. Reversing a number means changing the order of its digits from left to right. For example, reversing the number 12345 would result in 54321. We will discuss the problem statement, provide an explanation with suitable examples, present the pseudocode and algorithm for the recursive solution, and finally, provide an explanation of the resultant output with the time complexity of the code.

Problem Statement

The problem is to write a recursive function that takes an integer as input and returns its reverse as output. If the input number is positive, the function should reverse its digits and return the new number. If the input number is negative, the function should reverse its absolute value and then return the new number with a negative sign.

Explanation with Suitable Example

Let's take the number 12345 as an example. To reverse this number using recursion, we follow these steps:

  1. Extract the last digit of the number: 12345 % 10 = 5
  2. Recur with the remaining digits: reverse_num(1234, 5)
  3. Extract the last digit of the remaining number: 1234 % 10 = 4
  4. Recur with the remaining digits: reverse_num(123, 54)
  5. Repeat this process until no digits are left: reverse_num(1, 5432)

Now, the base condition is reached since 1 is less than or equal to 0. So, we return the result, which is 54321.

Pseudocode and Algorithm

The recursive function reverse_num(number, result) takes two parameters: number (the remaining digits) and result (the reversed number obtained so far).

The algorithm can be represented using standard pseudocode as follows:

function reverse_num(number, result):
    if number > 0:
        return reverse_num(number / 10, result * 10 + (number % 10))
    return result

function reverse(number):
    if number < 0:
        return -reverse_num(-number, 0)
    else:
        return reverse_num(number, 0)

Explanation of the Algorithm

  1. The reverse_num function takes two arguments: number and result. If the number is greater than 0, it means there are still digits left to process.
  2. In each recursive call, the last digit of the number is extracted using (number % 10) and added to the reversed result result * 10.
  3. The function is called recursively with the remaining digits obtained by dividing the number by 10 (number / 10).
  4. This process continues until there are no digits left (number <= 0), at which point the result is returned.
  5. The reverse function first checks if the input number is negative. If so, it calls reverse_num with the absolute value of the number and then returns the result with a negative sign.
  6. If the input number is positive, the reverse function directly calls reverse_num with the input number.

Program List

Resultant Output Explanation

Let's consider the provided test cases:

  1. For the number 12345:

    • Before reversing, the number is displayed as [12345].
    • After reversing, the output is [54321].
  2. For the number 78942:

    • Before reversing, the number is displayed as [78942].
    • After reversing, the output is [24987].
  3. For the number 1020:

    • Before reversing, the number is displayed as [1020].
    • After reversing, the output is [201].
  4. For the number -28:

    • Before reversing, the number is displayed as [-28].
    • After reversing, the output is [-82].

Time Complexity of the Code

The time complexity of the code is O(log N), where N is the input number. In each recursion, the input number is divided by 10 until it becomes 0. The number of recursive calls depends on the number of digits in the input number, which is logarithmic with respect to the input number. Hence, the time complexity is logarithmic.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment