print N to 1 using recursion

Description

Given a positive integer N, print all the numbers from N down to 1 in decreasing order without using any loops.

You must use recursion to achieve this. The numbers should be printed as space-separated values.

This problem is the mirror image of 'Print 1 to N'. While that problem taught you how the placement of the print statement relative to the recursive call controls output order, this problem reinforces that concept from the opposite direction. Here, printing BEFORE recursing naturally produces descending order.

Examples

Example 1

Input: N = 10

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

Explanation: Starting from 10, each number is printed in decreasing order down to 1. The function receives 10, prints it, then handles 9 through 1 recursively.

Example 2

Input: N = 5

Output: 5 4 3 2 1

Explanation: The function starts at N = 5, prints 5, then recursively prints 4, 3, 2, and 1. Each recursive call reduces N by 1 until the base case (N = 0) is reached, at which point the recursion stops.

Example 3

Input: N = 1

Output: 1

Explanation: With N = 1, the function prints 1 and then calls itself with N = 0, which triggers the base case. Only one number is printed.

Constraints

1 ≤ N ≤ 1000
Output must be space-separated integers in decreasing order
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 simplest way to print numbers from N down to 1 is to use a loop that starts at N and decrements until it reaches 1. This is the iterative approach — straightforward, uses O(1) extra space, and runs in O(N) time.

Think of it like counting down before a rocket launch: 10, 9, 8, ..., 3, 2, 1. You start at the highest number and work your way down, saying each number aloud as you go.

However, the problem forbids loops. We show this approach as the baseline to understand what the recursive solution must replicate: start at N, output each number, and decrease by 1 until we reach 1.

Step-by-Step Explanation

Let's trace the iterative approach with N = 5:

Step 1: Initialize loop variable i = 5 (start from N). Print 5.

Step 2: Decrement i to 4. Print 4.

Step 3: Decrement i to 3. Print 3.

Step 4: Decrement i to 2. Print 2.

Step 5: Decrement i to 1. Print 1.

Step 6: Decrement i to 0. Since 0 < 1, loop terminates.

Output: 5 4 3 2 1

This is clean and simple, but uses a loop. We need recursion to achieve the same countdown.

Algorithm

Initialize a counter i to N
While i ≥ 1:
a. Print i
b. Decrement i by 1
Done

Code

#include <iostream>
using namespace std;

void printNtoOne(int n) {
    // Iterative approach (violates the no-loop constraint)
    for (int i = n; i >= 1; i--) {
        cout << i << " ";
    }
}

int main() {
    int n = 5;
    printNtoOne(n);
    return 0;
}

def print_n_to_one(n):
    # Iterative approach (violates the no-loop constraint)
    for i in range(n, 0, -1):
        print(i, end=" ")

n = 5
print_n_to_one(n)

class Solution {
    public static void printNtoOne(int n) {
        // Iterative approach (violates the no-loop constraint)
        for (int i = n; i >= 1; i--) {
            System.out.print(i + " ");
        }
    }

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

Complexity Analysis

Time Complexity: O(N)

The loop runs exactly N times, performing one print per iteration. Total work scales linearly with N.

Space Complexity: O(1)

Only a single loop variable i is used. No additional memory grows with input size. However, this approach violates the problem's constraint of no loops.

Why This Approach Is Not Efficient

The iterative approach is time-and-space optimal (O(N) time, O(1) space), but it uses a loop, which is forbidden by the problem.

The problem's real purpose is to teach recursion — specifically, how a function can call itself with a smaller input to repeat an action. The challenge is: how do we count down from N to 1 using self-referential function calls?

The insight is surprisingly simple: if the function receives N, it should print N first, then ask itself to handle N-1, N-2, ..., all the way down to 1. Each recursive call is like delegating the remaining countdown to a copy of yourself that handles one fewer number.

The base case is when N reaches 0 (or less) — there's nothing left to print, so the function simply returns.

Better Approach - Direct Recursion (Print Before Recurse)

Intuition

Printing N down to 1 with recursion is actually the most natural use of recursion for printing — even simpler than printing 1 to N.

The function receives N. It prints N immediately. Then it calls itself with N-1 to handle the rest. Since N is printed before the recursive call, larger numbers appear first in the output. The recursion naturally produces descending order.

Imagine you are the host of a countdown show. You announce the current number (say, 5), then hand the microphone to the next host who announces 4, and so on. Each host says their number the moment they get the microphone (print first), then passes it to the next (recurse). When the microphone reaches the host for 0, they have nothing to say — they just leave (base case).

This is called head recursion or pre-order recursion: the work (printing) happens BEFORE the recursive call. Compare this to the 'Print 1 to N' problem where the optimal approach prints AFTER the recursive call to reverse the order.

Step-by-Step Explanation

Let's trace direct recursion with N = 5:

Step 1: Call printNos(5). Since 5 > 0, print 5 immediately. Output: '5'. Then call printNos(4).

Step 2: Call printNos(4). Since 4 > 0, print 4 immediately. Output: '5 4'. Then call printNos(3).

Step 3: Call printNos(3). Since 3 > 0, print 3 immediately. Output: '5 4 3'. Then call printNos(2).

Step 4: Call printNos(2). Since 2 > 0, print 2 immediately. Output: '5 4 3 2'. Then call printNos(1).

Step 5: Call printNos(1). Since 1 > 0, print 1 immediately. Output: '5 4 3 2 1'. Then call printNos(0).

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

Step 7: The call stack unwinds: printNos(0) returns to printNos(1), then to printNos(2), and so on. No additional printing happens during unwinding because all work was done before the recursive calls.

Output: 5 4 3 2 1

Direct Recursion — Print BEFORE the Recursive Call — Watch how each function prints its number immediately upon entry (before recursing), producing descending order naturally. All output happens during the winding phase.

Algorithm

Define function printNos(N)
Base case: If N ≤ 0, return (nothing to print)
Recursive step: Print N first, then call printNos(N - 1)
The initial call is simply printNos(N)

Why this works:

Printing N before the recursive call ensures the largest number appears first
The recursive call printNos(N-1) handles all numbers from N-1 down to 1
The base case prevents the recursion from going below 1

Code

#include <iostream>
using namespace std;

void printNos(int N) {
    // Base case: nothing left to print
    if (N == 0) return;
    
    // Print current number FIRST (descending order)
    cout << N << " ";
    
    // Then recurse to handle N-1 down to 1
    printNos(N - 1);
}

int main() {
    int N = 10;
    printNos(N);
    return 0;
}

def print_nos(N):
    # Base case: nothing left to print
    if N == 0:
        return
    
    # Print current number FIRST (descending order)
    print(N, end=" ")
    
    # Then recurse to handle N-1 down to 1
    print_nos(N - 1)

N = 10
print_nos(N)

class Solution {
    public static void printNos(int N) {
        // Base case: nothing left to print
        if (N == 0) return;
        
        // Print current number FIRST (descending order)
        System.out.print(N + " ");
        
        // Then recurse to handle N-1 down to 1
        printNos(N - 1);
    }

    public static void main(String[] args) {
        int N = 10;
        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 does O(1) work. Total time: O(N).

Space Complexity: O(N)

The maximum recursion depth is N + 1. Each frame on the call stack stores the parameter N and the return address. This uses O(N) space. For N = 1000 (the upper constraint), this means about 1000 stack frames, which is well within typical stack limits.

Why This Approach Is Not Efficient

The direct recursion approach works perfectly and meets the problem requirements. It uses O(N) time and O(N) stack space, which matches the expected complexities.

However, there is an alternative approach worth understanding: forward recursion (counting up) with printing after the recursive call. This approach starts from 1 and counts up to N, but delays printing until the recursive call returns. Since the deepest call (holding N) returns last, N is printed first, producing descending order.

Why learn this alternative? Because it demonstrates the same principle from the other side:

Print before recurse → output follows the calling order (descending: N, N-1, ..., 1)
Print after recurse → output follows the return order (ascending for 'Print 1 to N', but if we count up and print after, we get descending!)

Understanding both approaches solidifies your grasp of how the call stack's LIFO (Last In, First Out) nature can be leveraged to control output order.

Optimal Approach - Forward Recursion with Backtracking (Print After Recurse)

Intuition

Here is a clever alternative: instead of counting down from N to 1, we count up from 1 to N using a helper function with a counter i. But instead of printing i on the way up (which would give ascending order), we print i on the way back down — after the recursive call returns.

Wait, that would give ascending order (1, 2, 3, ..., N) as we saw in 'Print 1 to N'. How do we get descending order?

The trick: use a single parameter N and count down in the recursive call (printNos(N-1)), but place the print statement after the recursive call. The deepest call reaches printNos(1), which calls printNos(0) (base case). On the way back up, printNos(1) prints 1 first, then printNos(2) prints 2, and so on until printNos(N) prints N.

But that gives ascending order — 1, 2, ..., N — which is wrong for this problem!

So actually, the truly clever alternative is: count up using a helper printHelper(i, N), print i after the recursive call printHelper(i+1, N). Since the deepest call (where i = N) returns first, it prints N first. Then N-1, then N-2, ..., then 1. This gives descending order!

This approach demonstrates the same backtracking principle but applied inversely. In 'Print 1 to N', backward recursion (counting down, printing after) gave ascending output. Here, forward recursion (counting up, printing after) gives descending output. The LIFO nature of the stack always reverses the natural order.

Step-by-Step Explanation

Let's trace forward recursion with backtracking for N = 5:

Step 1: Call printHelper(1, 5). Since 1 ≤ 5, do NOT print yet. First, call printHelper(2, 5).

Step 2: Call printHelper(2, 5). Since 2 ≤ 5, do NOT print yet. First, call printHelper(3, 5).

Step 3: Call printHelper(3, 5). Since 3 ≤ 5, do NOT print yet. First, call printHelper(4, 5).

Step 4: Call printHelper(4, 5). Since 4 ≤ 5, do NOT print yet. First, call printHelper(5, 5).

Step 5: Call printHelper(5, 5). Since 5 ≤ 5, do NOT print yet. First, call printHelper(6, 5).

Step 6: Call printHelper(6, 5). Since 6 > 5, base case! Return.

Step 7: Back in printHelper(5, 5): recursive call returned. Now print 5. Output: '5'.

Step 8: Back in printHelper(4, 5): recursive call returned. Now print 4. Output: '5 4'.

Step 9: Back in printHelper(3, 5): recursive call returned. Now print 3. Output: '5 4 3'.

Step 10: Back in printHelper(2, 5): recursive call returned. Now print 2. Output: '5 4 3 2'.

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

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

Forward Recursion with Backtracking — Counting Up, Printing Down — Watch how the function counts up from 1 to N without printing, then prints each number during the unwinding phase in reverse order (N down to 1). The stack's LIFO property converts an ascending traversal into descending output.

Algorithm

Define helper function printHelper(i, N) that counts up from i to N
Base case: If i > N, return
Recursive step: First call printHelper(i + 1, N) (go deeper before printing)
Then print i (print AFTER the recursive call returns)
Start with printHelper(1, N)

Why this works:

The recursive call ensures all larger numbers (i+1 to N) are handled first
The deepest call (i = N) returns first and prints N first
Then i = N-1 prints, then N-2, ..., down to 1
The stack's LIFO property reverses the counting-up traversal into descending output

Code

#include <iostream>
using namespace std;

void printHelper(int i, int N) {
    // Base case: gone past N
    if (i > N) return;
    
    // FIRST recurse to handle i+1 through N
    printHelper(i + 1, N);
    
    // THEN print current number (after recursive call returns)
    // Deepest call (i=N) prints first → descending order
    cout << i << " ";
}

void printNos(int N) {
    printHelper(1, N);
}

int main() {
    int N = 10;
    printNos(N);
    return 0;
}

def print_helper(i, N):
    # Base case: gone past N
    if i > N:
        return
    
    # FIRST recurse to handle i+1 through N
    print_helper(i + 1, N)
    
    # THEN print current number (after recursive call returns)
    # Deepest call (i=N) prints first → descending order
    print(i, end=" ")

def print_nos(N):
    print_helper(1, N)

N = 10
print_nos(N)

class Solution {
    public static void printHelper(int i, int N) {
        // Base case: gone past N
        if (i > N) return;
        
        // FIRST recurse to handle i+1 through N
        printHelper(i + 1, N);
        
        // THEN print current number (after recursive call returns)
        // Deepest call (i=N) prints first → descending order
        System.out.print(i + " ");
    }

    public static void printNos(int N) {
        printHelper(1, N);
    }

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

Complexity Analysis

Time Complexity: O(N)

The helper function is called N + 1 times (from i = 1 to i = N + 1, where the last is the base case). Each call performs O(1) work. Total: O(N).

Space Complexity: O(N)

Maximum recursion depth is N + 1. Each stack frame stores i and N. Total stack space: O(N).

Comparison of both recursive approaches:

Aspect	Direct Recursion	Forward + Backtracking
Direction	Counts down (N → 1)	Counts up (1 → N)
Print position	Before recursive call	After recursive call
When output appears	During winding	During unwinding
Parameters	1 (N only)	2 (i and N)
Time	O(N)	O(N)
Space	O(N)	O(N)

Both approaches are equally valid. The direct recursion is simpler (single parameter), but the backtracking approach teaches the profound concept that the call stack acts as a reversal buffer — the same principle used in tree traversals, expression evaluation, and many advanced algorithms.

Key takeaway for both problems combined (Print 1→N and Print N→1):

Count down + print before = descending output
Count down + print after = ascending output
Count up + print before = ascending output
Count up + print after = descending output

The position of the print statement (before vs after the recursive call) always reverses the natural traversal order.

Language Essentials & Syntax

EASY

Pattern-Based Logic Building

EASY

Standard Libraries & Collections

EASY

Essential Mathematics

EASY

MEDIUM

Recursion Fundamentals

EASY

Hashing Essentials

EASY

MEDIUM

Comparison-Based Sorts

EASY

Divide & Conquer Sorts

EASY

MEDIUM

Array Fundamentals

EASY

MEDIUM

Intermediate Array Problems

EASY

MEDIUM

Advanced Array Challenges

EASY

MEDIUM

HARD

Searching in Sorted Arrays

EASY

MEDIUM

Search Space Reduction

EASY

MEDIUM

HARD

Matrix Binary Search

EASY

MEDIUM

HARD

Core String Operations

EASY

MEDIUM

Intermediate String Challenges

EASY

MEDIUM

Singly Linked List Basics

EASY

MEDIUM

Doubly Linked List Basics

EASY

MEDIUM

Linked List Techniques

EASY

MEDIUM

Doubly Linked List Techniques

MEDIUM

HARD

Advanced Linked List Challenges

MEDIUM

HARD

Building Recursive Thinking

EASY

MEDIUM

Generating Subsequences

EASY

MEDIUM

Exhaustive Search & Constraint Solving

MEDIUM

HARD

Bitwise Operations Fundamentals

EASY

MEDIUM

Bit Manipulation Applications

EASY

MEDIUM

Number Theory & Primes

EASY

MEDIUM

HARD