A function can call itself thanks to the effective programming technique known as recursion. This method can be applied to elegantly resolve issues that can be divided into smaller issues. Reversing a number is one such issue that can be resolved recursively by gradually extracting and adding the digits.
Reversing a number simply means changing the order of its digits. For example, reversing 123 would result in 321. Being able to reverse a number programmatically is a common interview question and a good way to get familiar with recursion.
In C, we can leverage recursion to reverse a number with just a few lines of code. The key is to continuously divide the number by 10, extract the last digit using the modulo operator, and accumulate it into the result. This article will walk through this recursive approach step-by-step.
Prerequisites
To follow along with this article, readers should have:
- Basic understanding of C programming constructs like functions, loops, and operators
- Familiarity with the modulo (%) operator and integer division
- Understanding of recursion and how recursive functions work
Overview Of Recursion in C
Recursion is a problem-solving method where a function repeatedly calls itself. The characteristics of a recursive function are as follows:
- Base case – A simple case where the function does not recurse further
- Recursive call – Function calling itself with different inputs
Recursion is useful when a problem can be broken down into simpler sub-problems. Each recursive call works on a smaller sub-problem until the base case is reached.
For example, calculating the factorial of a number lends itself well to a recursive solution:
int factorial(int n) {
if (n == 0) { // base case
return 1;
}
return n * factorial(n-1); // recursive call
}
Here, the factorial function calls itself with n-1 until n == 0. Recursion provides an elegant solution in this case.
Recursive Approach
The recursive approach is to successively extract the last digit and accumulate it into the result:
- Extract the last digit using % 10
- Append it to the recursive call operating on the remaining number (divided by 10)
- The recursion stops when the number becomes 0 (base case)
For example, to reverse 123:
- Extract 3, append it to reverse(12) => 3 + reverse(12)
- Extract 2, append it to reverse(1) => 3 + 2 + reverse(1)
- Extract 1, append it to reverse(0) => 3 + 2 + 1 + reverse(0)
- Base case, return 0
Here is a recursive pseudocode implementation:
reverse(num)
if num == 0
return 0
digit = num % 10
return digit + 10 * reverse(num / 10)
Implementation in C
Here is the C implementation of recursively reversing a number:
// Recursive function to reverse a number
int reverse(int num) {
// Base case
if (num == 0)
return 0;
// Extract last digit and append to reversed number
int digit = num % 10;
int reversed = digit + 10 * reverse(num / 10);
return reversed;
}
// Driver code
int main() {
int num = 12345;
int reversed = reverse(num);
printf("Reversed number is: %d", reversed);
return 0;
}
Output:
Reversed number is: 54321
- The reverse function is defined to reverse an integer num recursively.
- In the reverse function, there’s a base case: if num is equal to 0, it returns 0. This is the termination condition for the recursion.
- If num is not 0, it proceeds with the reversal process.
- The last digit of num is extracted using the modulo operator % and stored in the variable digit.
- The function then calls itself recursively with the remaining part of the number after removing the last digit (num / 10).
- The result of the recursive call is multiplied by 10 and added to the digit. This effectively appends the last digit to the reversed number.
- This process continues until the base case is reached, and the recursion starts to unwind.
- The reversed number is built up as the recursion unwinds, and eventually, the fully reversed number is returned.
- In the main function, an integer num is initialized with the value 12345.
- The reverse function is called with num, and the result is stored in the reversed variable.
- Finally, the reversed number is printed using printf.
This recursively extracts and accumulates each digit to build the final reversed number.
Time and Space Complexity
The time complexity of the algorithm is denoted as O(n), where ‘n’ signifies the count of digits in the input. This complexity arises from the fact that the algorithm involves extracting a digit and making a recursive call for each digit in the input, leading to a linear relationship between the execution time and the size of the input.
On the other hand, the space complexity is also O(n). This is primarily due to the space required for the recursion stack, which grows in proportion to the number of recursive calls made by the algorithm. Since the number of recursive calls is directly tied to the size of the input (number of digits), the space complexity is linear relative to the input size.
Conclusion
This article demonstrated how to recursively reverse a number in C – from the concept and algorithm to implementation and testing. The elegance of recursion lies in breaking a problem down into simpler sub-problems.
Mastering recursion in C will equip you with a powerful technique to solve a variety of algorithmic problems. Starting with reversing a number serves as an excellent first step. Readers are encouraged to apply recursion to other problems like computing Fibonacci numbers.