Given a non-negative integer n, print all numbers from 1 to n in strictly increasing order using recursion.
Example 1
Input: n = 4
Output: 1 2 3 4
Explanation: The sequence begins at 1 and increments consecutively until it reaches the target integer 4.
Example 2
Input: n = 2
Output: 1 2
Explanation: The sequence counts upward and cleanly stops exactly after printing the target integer 2.
Approach
A recursive call with n - 1 naturally moves from a larger number toward 1.
However, printing n before the recursive call would produce the numbers in decreasing order. To get increasing order, the print statement is placed after the recursive call.
This allows the function to first reach the smallest value. The numbers are then printed one by one while the recursive calls return, giving the order 1, 2, 3, ..., n.
Algorithm
Define a recursive function that takes
nas its parameter, wherenrepresents the current largest number that still needs to be printed.When
n <= 0, return from the function because there is no positive number left to process. This also safely handles zero or negative input.Call the function with
n - 1before printing the current value. This ensures that all smaller numbers are handled first.Print
nafter the recursive call returns. Since the calls return from the smallest value to the largest, the numbers appear in increasing order.
Dry Run
Print 1 to N Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: void printOneToN(int n) { // Base case: stop when no positive number is left. if (n <= 0) { return; } // Print the smaller numbers before the current number. printOneToN(n - 1); cout << n << " "; }};int main() { int n = 4; Solution solution; solution.printOneToN(n); cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because the function processes each number from N down to 1 once.
Space Complexity: O(N), because N recursive calls remain stored in the call stack before the printing begins.
FAQs
Q1. Why is the print statement placed after the recursive call?
Placing it after the recursive call allows all smaller values to be processed first. The numbers are then printed while the calls return, which produces increasing order.
Q2. What happens if the print statement is placed before the recursive call?
The current value would be printed immediately, so the output would appear in decreasing order from N to 1.
Q3. What is printed when n = 0?
Nothing is printed because the base case is reached in the first call.
Q4. Why is n <= 0 used instead of only n == 0?
Using n <= 0 also stops the recursion safely when a negative value is passed.
Q5. Can this problem be solved without recursion?
Yes. A loop can print the numbers using O(1) auxiliary space. Recursion is used here to understand how statement placement affects the order in which results are produced.
Q6. Is this an example of backtracking?
Yes. The print statement runs while the recursive calls return, so the output is produced during the backtracking phase.
Be the first to add a comment.