Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

print 1 to N using recursion

EASYProblemSolveExternal Links

Description

Given a positive integer n, print all the numbers from 1 to n in increasing order without using any loops (no for, while, or do-while).

You must use recursion — a technique where a function calls itself to solve smaller instances of the same problem. The function should print the numbers as space-separated values.

This is a foundational recursion problem that teaches you how to control the order of operations using recursive calls and where you place the print statement relative to the recursive call.

Examples

Example 1

Input: n = 5

Output: 1 2 3 4 5

Explanation: The function prints every integer starting from 1 up to 5 in ascending order. Even though the function receives n = 5 first, it must delay printing 5 until all smaller numbers (1 through 4) have been printed.

Example 2

Input: n = 1

Output: 1

Explanation: With n = 1, the function hits the base case immediately. There is only one number to print, so the output is just 1. This is the simplest case and the foundation that all larger inputs build upon.

Example 3

Input: n = 10

Output: 1 2 3 4 5 6 7 8 9 10

Explanation: The function recursively descends from 10 all the way down to 1 (the base case), then prints each number on the way back up the call stack. This produces the ascending order 1 through 10.

Constraints

  • 1 ≤ n ≤ 1000
  • Output must be space-separated integers
  • No loops allowed — must use recursion
  • Expected Time Complexity: O(n)
  • Expected Auxiliary Space: O(n) due to the recursion call stack

Editorial

Brute Force

Intuition

The most natural way to print numbers 1 to n is to use a simple loop — iterate from 1 to n and print each number. While this approach is correct, the problem explicitly forbids using loops, so we present it as the brute force to show what we are trying to replicate with recursion.

Think of it like counting on your fingers from 1 to 5. You simply go through each finger one by one in order. A loop does exactly this — it starts at 1, prints it, moves to 2, prints it, and so on until it reaches n.

The brute force establishes the baseline: we need O(n) time and we need the numbers to appear in ascending order. Our goal with recursion is to achieve the same result without any loop construct.

Step-by-Step Explanation

Let's trace through the iterative approach with n = 5:

Step 1: Initialize loop variable i = 1. Print 1.

Step 2: Increment i to 2. Print 2.

Step 3: Increment i to 3. Print 3.

Step 4: Increment i to 4. Print 4.

Step 5: Increment i to 5. Print 5.

Step 6: i becomes 6, which is > n = 5. Loop terminates.

Output: 1 2 3 4 5

This is straightforward but uses a for loop, which violates the problem constraint. We need an alternative mechanism that repeats an action n times — and that mechanism is recursion.

Algorithm

  1. Initialize a counter i to 1
  2. While i ≤ n:
    a. Print i
    b. Increment i by 1
  3. Done

Code

#include <iostream>
using namespace std;

void printTillN(int n) {
    // Simple loop approach (violates constraint but shows baseline)
    for (int i = 1; i <= n; i++) {
        cout << i << " ";
    }
}

int main() {
    int n = 5;
    printTillN(n);
    return 0;
}
def print_till_n(n):
    # Simple loop approach (violates constraint but shows baseline)
    for i in range(1, n + 1):
        print(i, end=" ")

n = 5
print_till_n(n)
class Solution {
    public static void printTillN(int n) {
        // Simple loop approach (violates constraint but shows baseline)
        for (int i = 1; i <= n; i++) {
            System.out.print(i + " ");
        }
    }

    public static void main(String[] args) {
        int n = 5;
        printTillN(n);
    }
}

Complexity Analysis

Time Complexity: O(n)

The loop runs exactly n times, performing one print operation per iteration. Total work is linear in n.

Space Complexity: O(1)

Only a single loop variable i is used. No additional memory grows with input size. However, this approach uses a loop, which is not allowed by the problem constraints.

Why This Approach Is Not Efficient

The iterative approach is actually optimal in terms of time and space — O(n) time and O(1) space. However, the problem explicitly forbids loops. This is not a performance constraint but a structural constraint: we must use recursion.

The purpose of this problem is to teach you how recursion can replace loops. The key insight is:

  • A loop repeats an action by incrementing a counter
  • Recursion repeats an action by calling itself with a modified argument

Both achieve repetition, but recursion uses the call stack to track where it is, while a loop uses a variable. The trade-off: recursion uses O(n) stack space (one stack frame per call), but it lets us avoid explicit loop constructs.

The next approach shows how to use forward recursion — counting up from 1 — to achieve the same ascending output.

Better Approach - Forward Recursion (Counting Up)

Intuition

The most straightforward recursive replacement for a loop is forward recursion — we start from 1 and count upward, printing each number before making the next recursive call.

Imagine you are a relay runner in a race with n legs. You are runner #1. You run your leg (print 1), then hand the baton to runner #2 who prints 2, and so on. Each runner does their job and passes work to the next one. When runner n finishes, the relay is complete.

In code, we define a helper function that takes the current number i and the target n. It prints i, then calls itself with i + 1. The base case is when i > n — there are no more numbers to print.

This approach mirrors the loop directly: the current value i plays the role of the loop variable, and the recursive call replaces the loop's increment.

Step-by-Step Explanation

Let's trace forward recursion with n = 5:

Step 1: Call printNos(1, 5). Since 1 ≤ 5, print 1. Then call printNos(2, 5).

Step 2: Call printNos(2, 5). Since 2 ≤ 5, print 2. Then call printNos(3, 5).

Step 3: Call printNos(3, 5). Since 3 ≤ 5, print 3. Then call printNos(4, 5).

Step 4: Call printNos(4, 5). Since 4 ≤ 5, print 4. Then call printNos(5, 5).

Step 5: Call printNos(5, 5). Since 5 ≤ 5, print 5. Then call printNos(6, 5).

Step 6: Call printNos(6, 5). Since 6 > 5, base case reached — return without printing.

Step 7: All recursive calls return. The call stack unwinds: printNos(5,5) returns to printNos(4,5), which returns to printNos(3,5), and so on back to the original call.

Output: 1 2 3 4 5 — printed in order because we print BEFORE the recursive call.

Forward Recursion — Counting Up from 1 to 5 — Watch how each recursive call prints the current number BEFORE calling the next, producing ascending order. The call stack grows until the base case, then unwinds.

Algorithm

  1. Define a helper function printNos(i, n) that takes the current number i and the upper limit n
  2. Base case: If i > n, return (nothing left to print)
  3. Recursive step: Print i, then call printNos(i + 1, n)
  4. Start the recursion by calling printNos(1, n)

Code

#include <iostream>
using namespace std;

void printNos(int i, int n) {
    // Base case: if i exceeds n, stop recursion
    if (i > n) return;
    
    // Print current number first (ascending order)
    cout << i << " ";
    
    // Recurse with next number
    printNos(i + 1, n);
}

int main() {
    int n = 5;
    printNos(1, n);
    return 0;
}
def print_nos(i, n):
    # Base case: if i exceeds n, stop recursion
    if i > n:
        return
    
    # Print current number first (ascending order)
    print(i, end=" ")
    
    # Recurse with next number
    print_nos(i + 1, n)

n = 5
print_nos(1, n)
class Solution {
    public static void printNos(int i, int n) {
        // Base case: if i exceeds n, stop recursion
        if (i > n) return;
        
        // Print current number first (ascending order)
        System.out.print(i + " ");
        
        // Recurse with next number
        printNos(i + 1, n);
    }

    public static void main(String[] args) {
        int n = 5;
        printNos(1, n);
    }
}

Complexity Analysis

Time Complexity: O(n)

The function is called exactly n + 1 times: once for each number from 1 to n, plus one base case call. Each call does O(1) work (one print and one comparison). Total time: O(n).

Space Complexity: O(n)

Each recursive call adds a frame to the call stack. The maximum recursion depth is n + 1 (from printNos(1, n) all the way to printNos(n+1, n) which is the base case). So the call stack uses O(n) space.

This is the trade-off compared to the iterative approach: we gain the ability to avoid loops, but we pay with O(n) stack space instead of O(1).

Why This Approach Is Not Efficient

The forward recursion approach works correctly and meets the problem requirements. However, it requires an extra parameter — the helper function needs both i (current number) and n (upper limit). This means the caller must know to pass 1 as the starting value, which is slightly awkward.

A more elegant approach exists: backward recursion (backtracking). Instead of counting up from 1 to n, we can count down from n to 1, but print after the recursive call returns. This way, the function signature matches the problem's signature — it only takes a single parameter n.

The key insight: by placing the print statement after the recursive call instead of before it, we reverse the output order. Recursing first (going deeper before printing) means the deepest call prints first (which holds the smallest number), producing ascending order.

This is an important recursion concept: the placement of work relative to the recursive call determines the order of operations.

Optimal Approach - Backward Recursion (Backtracking / Print After Recurse)

Intuition

Instead of carrying an extra counter i, we can use a single parameter n and count backward. The trick is to place the print statement after the recursive call, not before it.

Imagine a line of dominoes numbered 1 to 5 standing upright. You push domino 5, which knocks over domino 4, which knocks over 3, then 2, then 1. But the catch: each domino only reveals its number after it has been knocked down. Since domino 1 falls last (hits the ground first in the chain), it reveals its number first. Then domino 2 reveals, then 3, 4, and finally 5.

In code:

  • printNos(5) calls printNos(4) first (before printing 5)
  • printNos(4) calls printNos(3) first (before printing 4)
  • This continues until printNos(0) is reached — the base case
  • Then each function prints its number as it returns: 1, 2, 3, 4, 5

The output comes out in ascending order even though the function receives numbers in descending order. This is because the print statement executes during the unwinding phase of recursion, not the winding phase.

Step-by-Step Explanation

Let's trace backward recursion with n = 5:

Step 1: Call printNos(5). Since 5 > 0, do NOT print yet. First, call printNos(4).

Step 2: Call printNos(4). Since 4 > 0, do NOT print yet. First, call printNos(3).

Step 3: Call printNos(3). Since 3 > 0, do NOT print yet. First, call printNos(2).

Step 4: Call printNos(2). Since 2 > 0, do NOT print yet. First, call printNos(1).

Step 5: Call printNos(1). Since 1 > 0, do NOT print yet. First, call printNos(0).

Step 6: Call printNos(0). Since 0 ≤ 0, base case! Return without doing anything.

Step 7: Back in printNos(1): the recursive call returned. Now print 1. Output: '1'.

Step 8: Back in printNos(2): the recursive call returned. Now print 2. Output: '1 2'.

Step 9: Back in printNos(3): the recursive call returned. Now print 3. Output: '1 2 3'.

Step 10: Back in printNos(4): the recursive call returned. Now print 4. Output: '1 2 3 4'.

Step 11: Back in printNos(5): the recursive call returned. Now print 5. Output: '1 2 3 4 5'.

Step 12: All calls returned. Final output: '1 2 3 4 5'.

Backward Recursion — Print AFTER the Recursive Call — Watch how the function descends from n to 0 without printing anything, then prints each number during the unwinding phase (backtracking), producing ascending order from a descending countdown.

Algorithm

  1. Define function printNos(n)
  2. Base case: If n ≤ 0, return (recursion stops)
  3. Recursive step: First call printNos(n - 1) (recurse to smaller value)
  4. Then print n (print AFTER the recursive call returns)
  5. The initial call is simply printNos(n) — no extra parameter needed

Why this works:

  • The recursive call printNos(n-1) ensures all numbers from 1 to n-1 are printed first
  • Only after that entire sub-problem is solved does the current call print n
  • This guarantees ascending order: 1, 2, 3, ..., n

Code

#include <iostream>
using namespace std;

void printNos(int n) {
    // Base case: nothing to print
    if (n == 0) return;
    
    // FIRST recurse to handle all smaller numbers
    printNos(n - 1);
    
    // THEN print current number (after recursive call returns)
    // This ensures 1..n-1 are printed before n
    cout << n << " ";
}

int main() {
    int n = 5;
    printNos(n);
    return 0;
}
def print_nos(n):
    # Base case: nothing to print
    if n == 0:
        return
    
    # FIRST recurse to handle all smaller numbers
    print_nos(n - 1)
    
    # THEN print current number (after recursive call returns)
    # This ensures 1..n-1 are printed before n
    print(n, end=" ")

n = 5
print_nos(n)
class Solution {
    public static void printNos(int n) {
        // Base case: nothing to print
        if (n == 0) return;
        
        // FIRST recurse to handle all smaller numbers
        printNos(n - 1);
        
        // THEN print current number (after recursive call returns)
        // This ensures 1..n-1 are printed before n
        System.out.print(n + " ");
    }

    public static void main(String[] args) {
        int n = 5;
        printNos(n);
    }
}

Complexity Analysis

Time Complexity: O(n)

The function makes exactly n + 1 calls: printNos(n), printNos(n-1), ..., printNos(1), printNos(0). Each call performs O(1) work (one comparison + at most one print). Total time is O(n).

Space Complexity: O(n)

The call stack reaches a maximum depth of n + 1 before the base case is hit and unwinding begins. Each stack frame stores the local value of n and the return address. Total stack space: O(n).

Both the forward and backward approaches have identical time and space complexity. The difference is purely structural:

  • Forward recursion uses two parameters (i, n) and prints during the winding phase
  • Backward recursion uses one parameter (n) and prints during the unwinding phase

The backward approach is considered more elegant because it matches the problem's function signature (single parameter n) and demonstrates the powerful concept of backtracking — doing work after the recursive call returns.