Recursion via Repeated Printing
Description
You are given a positive integer n. Your task is to print all numbers from 1 to n in ascending order, each separated by a space.
The catch: you are not allowed to use any loops (no for, while, or do-while). You must accomplish this using recursion only.
This problem is a foundational exercise in understanding how recursion can replace iterative constructs. It teaches you to think about base cases, recursive calls, and the order in which operations happen relative to the recursive call (before or after).
Examples
Example 1
Input: n = 5
Output: 1 2 3 4 5
Explanation: We need to print every integer starting from 1 up to 5. The output is a space-separated sequence of these numbers in ascending order.
Example 2
Input: n = 10
Output: 1 2 3 4 5 6 7 8 9 10
Explanation: All integers from 1 through 10 are printed in increasing order. Even though the input is larger, the recursion handles it by making 10 nested calls before unwinding.
Example 3
Input: n = 1
Output: 1
Explanation: The simplest case — there is only one number to print. The recursion hits the base case almost immediately and prints just 1.
Constraints
- 1 ≤ n ≤ 10^3
- No loops allowed — recursion only
Editorial
Brute Force
Intuition
The most straightforward way to think about printing 1 to n is to count upward: start a counter at 1, print it, increment to 2, print it, and so on until you reach n. With a loop this would be trivial — but loops are forbidden.
So how can recursion replace a loop? Think of recursion as a chain of function calls. Each call can do a small piece of work (print one number) and then delegate the rest of the work to the next call. We need a counting-up recursive function.
The idea: create a function that takes a current value i and the target n. It prints i, then calls itself with i + 1. It stops when i exceeds n.
This is sometimes called head-first printing because we print at the beginning of each call before recursing deeper.
Step-by-Step Explanation
Let's trace through with n = 5:
Step 1: Call printUp(1, 5). Since 1 ≤ 5, print "1". Then call printUp(2, 5).
Step 2: Call printUp(2, 5). Since 2 ≤ 5, print "2". Then call printUp(3, 5).
Step 3: Call printUp(3, 5). Since 3 ≤ 5, print "3". Then call printUp(4, 5).
Step 4: Call printUp(4, 5). Since 4 ≤ 5, print "4". Then call printUp(5, 5).
Step 5: Call printUp(5, 5). Since 5 ≤ 5, print "5". Then call printUp(6, 5).
Step 6: Call printUp(6, 5). Since 6 > 5, this is the base case — return without printing. The recursion starts unwinding.
Result: Output is "1 2 3 4 5".
Counting-Up Recursion: printUp(1, 5) — Watch how each recursive call prints the current number before diving deeper, and the base case stops the chain when we exceed n.
Algorithm
- Define a recursive function
printUp(i, n)that takes the current numberiand the targetn - Base case: If
i > n, return without doing anything - Print the value of
i - Recursively call
printUp(i + 1, n)to handle the next number - The initial call is
printUp(1, n)
Code
#include <iostream>
using namespace std;
class Solution {
public:
void printUp(int i, int n) {
// Base case: stop when i exceeds n
if (i > n) return;
// Print current number
cout << i << " ";
// Recurse for the next number
printUp(i + 1, n);
}
void printNos(int n) {
printUp(1, n);
}
};
int main() {
Solution sol;
int n = 5;
sol.printNos(n);
return 0;
}class Solution:
def printNos(self, n: int) -> None:
self._printUp(1, n)
def _printUp(self, i: int, n: int) -> None:
# Base case: stop when i exceeds n
if i > n:
return
# Print current number
print(i, end=" ")
# Recurse for the next number
self._printUp(i + 1, n)
# Driver code
if __name__ == "__main__":
sol = Solution()
sol.printNos(5)class Solution {
private void printUp(int i, int n) {
// Base case: stop when i exceeds n
if (i > n) return;
// Print current number
System.out.print(i + " ");
// Recurse for the next number
printUp(i + 1, n);
}
public void printNos(int n) {
printUp(1, n);
}
public static void main(String[] args) {
Solution sol = new Solution();
sol.printNos(5);
}
}Complexity Analysis
Time Complexity: O(n)
We make exactly n recursive calls (plus one base case call), and each call performs O(1) work (one print statement). So the total time is O(n).
Space Complexity: O(n)
Each recursive call adds a frame to the call stack. Since the recursion goes n levels deep before hitting the base case and unwinding, the call stack uses O(n) space. This is the cost of replacing a loop with recursion.
Why This Approach Is Not Efficient
The counting-up approach works correctly but requires two parameters — the current counter i and the target n. This means the caller must know to start with i = 1, which is an extra detail.
More importantly, from an educational standpoint, this approach doesn't fully exploit the power of recursion. It essentially mimics a loop by incrementing a counter. A more elegant recursive solution would use only the parameter n and leverage the natural unwinding of the call stack to achieve the correct print order.
The key insight: if we first recurse to smaller values and then print on the way back up (after the recursive call returns), we can print in ascending order using only a single parameter. This teaches a deeper understanding of how the call stack works — specifically, how operations placed after a recursive call execute in reverse order of the recursion.
Optimal Approach - Post-Recursion Printing
Intuition
Here is the elegant insight: instead of counting up from 1 to n, we can count down from n to 1 in our recursive calls, but print after the recursive call returns.
Imagine you're standing in a line of n people. You tap the person in front of you and say "pass the message forward." That person taps the next, and so on, until the message reaches the front (person 1). Person 1 says their number out loud. Then person 2 says theirs. Then person 3, and so on, back to you. The numbers come out in order 1, 2, 3, ..., n — even though the passing went n, n-1, ..., 1.
This works because of how the call stack operates:
- When we call
printNos(n), it first callsprintNos(n-1)before doing anything else printNos(n-1)callsprintNos(n-2), and so on- Eventually
printNos(1)callsprintNos(0), which hits the base case and returns - Now
printNos(1)resumes and prints 1 - Then
printNos(2)resumes and prints 2 - This continues until
printNos(n)finally prints n
The print statements execute during the unwinding of the recursion, producing ascending order from a descending recursion.
Step-by-Step Explanation
Let's trace through with n = 5:
Step 1: Call printNos(5). Since 5 > 0, don't print yet — first recurse with printNos(4).
Step 2: Call printNos(4). Since 4 > 0, don't print yet — first recurse with printNos(3).
Step 3: Call printNos(3). Since 3 > 0, don't print yet — first recurse with printNos(2).
Step 4: Call printNos(2). Since 2 > 0, don't print yet — first recurse with printNos(1).
Step 5: Call printNos(1). Since 1 > 0, don't print yet — first recurse with printNos(0).
Step 6: Call printNos(0). Since 0 ≤ 0, BASE CASE — return immediately.
Step 7: Back in printNos(1): the recursive call returned. Now print "1". Output so far: "1".
Step 8: Back in printNos(2): the recursive call returned. Now print "2". Output so far: "1 2".
Step 9: Back in printNos(3): the recursive call returned. Now print "3". Output so far: "1 2 3".
Step 10: Back in printNos(4): the recursive call returned. Now print "4". Output so far: "1 2 3 4".
Step 11: Back in printNos(5): the recursive call returned. Now print "5". Final output: "1 2 3 4 5".
Post-Recursion Printing: printNos(5) — Unwind to Print — Watch how the recursion dives all the way down to the base case first, then prints numbers in ascending order as each call unwinds back up the stack.
Algorithm
- Define a recursive function
printNos(n) - Base case: If
n ≤ 0, return without doing anything - Recursive step: First call
printNos(n - 1)— this handles all smaller numbers - Post-recursion action: After the recursive call returns, print
n - The initial call is simply
printNos(n)
Code
#include <iostream>
using namespace std;
class Solution {
public:
void printNos(int n) {
// Base case: nothing to print
if (n <= 0) return;
// First, handle all numbers smaller than n
printNos(n - 1);
// After smaller numbers are printed, print n
cout << n << " ";
}
};
int main() {
Solution sol;
sol.printNos(5);
return 0;
}class Solution:
def printNos(self, n: int) -> None:
# Base case: nothing to print
if n <= 0:
return
# First, handle all numbers smaller than n
self.printNos(n - 1)
# After smaller numbers are printed, print n
print(n, end=" ")
# Driver code
if __name__ == "__main__":
sol = Solution()
sol.printNos(5)class Solution {
public void printNos(int n) {
// Base case: nothing to print
if (n <= 0) return;
// First, handle all numbers smaller than n
printNos(n - 1);
// After smaller numbers are printed, print n
System.out.print(n + " ");
}
public static void main(String[] args) {
Solution sol = new Solution();
sol.printNos(5);
}
}Complexity Analysis
Time Complexity: O(n)
We make exactly n + 1 function calls (n calls that print plus 1 base case call). Each call performs O(1) work. Total time is O(n).
Space Complexity: O(n)
The recursion goes n levels deep before the base case triggers and the stack begins unwinding. Each level occupies one stack frame, so the call stack uses O(n) space.
Note: Both approaches (counting-up and post-recursion) have identical time and space complexity. The difference is in elegance and the number of parameters — this approach uses only one parameter n, while the brute force used two (i and n). More importantly, this approach teaches the critical concept of how placing operations before vs. after a recursive call controls the order of execution.