Reverse a Number Using Recursion: flowchart, algorithm and program
This program reads an integer n and prints its digits in reverse order using a recursive function. Each call prints the last digit with n % 10 and then calls itself with n / 10 to handle the remaining digits.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read n.
- Step 3: Print "Reversed: ".
- Step 4: If n == 0, go to step 5; otherwise go to step 6.
- Step 5: Print 0. Go to step 9.
- Step 6: If n == 0? (reverse), go to step 9; otherwise go to step 7.
- Step 7: Print n % 10.
- Step 8: Set n = n / 10, call reverse(n). Go to step 6.
- Step 9: Print newline.
- Step 10: Stop.
Program in C, Python and Java
Reverse a Number Using Recursion program in C
#include <stdio.h>
void reverse(int n) {
if (n == 0)
return;
printf("%d", n % 10);
reverse(n / 10);
}
int main() {
int n;
printf("Enter n: ");
scanf("%d", &n);
printf("Reversed: ");
if (n == 0)
printf("0");
else
reverse(n);
printf("\n");
return 0;
}Reverse a Number Using Recursion program in Python
def reverse(n):
if n == 0:
return
print(n % 10, end="")
reverse(n // 10)
n = int(input("Enter n: "))
print("Reversed: ", end="")
if n == 0:
print("0", end="")
else:
reverse(n)
print()Reverse a Number Using Recursion program in Java
import java.util.Scanner;
public class Main {
static void reverse(int n) {
if (n == 0)
return;
System.out.print(n % 10);
reverse(n / 10);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
System.out.print("Reversed: ");
if (n == 0)
System.out.print("0");
else
reverse(n);
System.out.println();
}
}
Sample input: n = 12345
Output: Reversed: 54321
How it works
- reverse(n) first checks the base case: if n == 0, it returns and the recursion stops.
- Otherwise it prints n % 10, which is the last digit of n, so the digits come out right to left.
- Then it calls reverse(n / 10). Integer division drops the last digit, so the number gets shorter by one digit on every call.
- For n = 12345 the calls print 5, 4, 3, 2, 1 and then reverse(0) returns, giving 54321.
- main() handles n == 0 separately and prints 0 directly. Without that, reverse(0) would hit the base case at once and print nothing.
Dry run (trace table)
| Step | Line | Box | n | Output |
|---|---|---|---|---|
| 1 | 10 | Start | ||
| 2 | 13 | Read n | 12345 | |
| 3 | 14 | Print "Reversed: " | 12345 | Reversed: |
| 4 | 15 | n == 0? | 12345 | |
| 5 | 4 | n == 0? (reverse) | 12345 | |
| 6 | 6 | Print n % 10 | 12345 | 5 |
| 7 | 7 | n = n / 10, call reverse(n) | 1234 | |
| 8 | 4 | n == 0? (reverse) | 1234 | |
| 9 | 6 | Print n % 10 | 1234 | 4 |
| 10 | 7 | n = n / 10, call reverse(n) | 123 | |
| 11 | 4 | n == 0? (reverse) | 123 | |
| 12 | 6 | Print n % 10 | 123 | 3 |
| 13 | 7 | n = n / 10, call reverse(n) | 12 | |
| 14 | 4 | n == 0? (reverse) | 12 | |
| 15 | 6 | Print n % 10 | 12 | 2 |
| 16 | 7 | n = n / 10, call reverse(n) | 1 | |
| 17 | 4 | n == 0? (reverse) | 1 | |
| 18 | 6 | Print n % 10 | 1 | 1 |
| 19 | 7 | n = n / 10, call reverse(n) | 0 | |
| 20 | 4 | n == 0? (reverse) | 0 |
Time and space complexity
Time: O(log n) · Space: O(log n). Each recursive call removes one decimal digit, giving about log10(n) calls on the call stack.
Common mistakes
- Leaving out the n == 0 check in main(), so an input of 0 prints nothing instead of 0.
- Forgetting the base case in reverse(), which leads to infinite recursion and a stack overflow.
- Using n / 10 and n % 10 the wrong way round, or making the recursive call before the printf, which prints the digits in the original order instead of reversed.
Viva questions
Q1. What is the base case in reverse(), and why is it needed?
The base case is `if (n == 0) return;` on lines 4-5. Without it the function would call itself forever and the program would crash with a stack overflow.
Q2. What do n % 10 and n / 10 do here?
n % 10 gives the last digit of n, which is printed. n / 10 is integer division and drops that last digit, so the recursive call gets a smaller number.
Q3. Trace the program for n = 123. What is printed and in what order?
reverse(123) prints 3, reverse(12) prints 2, reverse(1) prints 1, and reverse(0) returns. The output is 321. The digit is printed before the recursive call, so digits come out last-first.
Q4. Why does main() handle n == 0 separately (lines 15-16)?
reverse(0) hits the base case straight away and prints nothing. Without the special case, an input of 0 would show an empty result instead of 0.
Q5. What happens for a negative input such as -45?
In C, -45 % 10 is -5 and -45 / 10 is -4, so the program prints -5 and then -4, giving '-5-4'. That is wrong output. Negative numbers should be converted with n = -n and the sign printed separately.
Q6. What happens if the number ends in zeros, for example n = 1200? Does this program really 'reverse the number'?
It prints 0021, including the leading zeros, because it prints digits rather than building a number. As a number, the reverse would be 21. To get a numeric value you would have to accumulate rev = rev*10 + digit instead of printing.
Q7. What is the time and space complexity of this program?
Time is O(d), where d is the number of digits (about log10 n), since each call removes one digit. Space is also O(d) because of the recursion stack, with one frame per digit.
Q8. What would change if you moved printf (line 6) after the recursive call on line 7?
The digits would be printed in their original order. For 123 the calls go down to reverse(0) first, then print 1, 2, 3 as they return. Printing before the call gives reverse order, and printing after the call gives the original order.
Frequently asked questions
Why does the digit get printed before the recursive call?
Printing n % 10 first outputs the last digit first, which gives the reversed order. If you made the recursive call first and printed afterwards, the digits would come out in the original order.
What is the base case in this recursive reverse function?
The base case is n == 0. When all digits have been removed by repeated division by 10, n becomes 0 and the function returns without printing.
Does this program store the reversed number as an integer?
No, it only prints the digits one by one. To get a reversed integer value you would need to build it up, for example by passing a running result as an extra parameter.
What happens with negative numbers or numbers ending in zero?
A number like 1200 prints 0021, because the trailing zeros are printed as leading digits. Negative input is not handled properly, since n % 10 can be negative in C and the output would be wrong.