☕ DSA Java Articles

Topics › Basics › Learn Basic Recursion

Print N to 1 using Recursion

Easy TUF ID 852 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a positive integer N. Print the numbers N, N - 1, ..., 2, 1 in decreasing order without using a loop; recursion is the only form of repetition allowed.

The task is the mirror image of printing 1 to N. It is worth doing separately because it shows that the direction of the output is controlled by two independent choices: which value the first call starts at, and whether the work happens before or after the recursive call. Change either choice and the output flips.

Constraints: 1 ≤ N ≤ 10^4. We treat N ≤ 0 as “print nothing” so the base case gets exercised.

The methods below collect the numbers into a List<Integer> so that the tests can assert on them; replacing out.add(x) with System.out.println(x) gives the printing version.

Example 1

N = 5
output = 5 4 3 2 1        // count down from N to 1

Example 2

N = 1
output = 1                // smallest valid input, one number

Example 3

N = 0
output = (nothing)        // no number lies between N and 1

Approach 1: The loop, as a reference

Intuition. A countdown loop starts the counter at N, emits it, and decrements until it drops below 1. Writing this down first tells us precisely what each recursive version has to reproduce.

Algorithm.

  1. Create an empty list.
  2. For i from N down to 1, append i.
  3. Return the list.
static List<Integer> iterative(int n) {
    List<Integer> out = new ArrayList<>();
    for (int i = n; i >= 1; i--) out.add(i);
    return out;
}

Complexity. Time O(n), one append per number. Space O(1) beyond the output list.

Approach 2: Parameterised recursion, work first then recurse

Intuition. Turn the loop counter into a parameter. The first call receives i = N; it emits i and then delegates i - 1 to the next call. The loop’s exit condition i < 1 becomes the base case. Because the value is emitted before the recursive call, the output is produced on the way down the call chain, and since we start at N and shrink, the numbers appear in decreasing order.

Compare this with the forward version of printing 1 to N: there the parameter starts at 1 and grows. Same shape, different start and step.

Algorithm.

  1. Start with forward(n, out).
  2. In forward(i, out): if i < 1, return (base case).
  3. Otherwise append i, then call forward(i - 1, out).
static List<Integer> recursiveForward(int n) {
    List<Integer> out = new ArrayList<>();
    forward(n, out);
    return out;
}

private static void forward(int i, List<Integer> out) {
    if (i < 1) return;          // base case: we have gone below 1
    out.add(i);                 // do the work ...
    forward(i - 1, out);        // ... then recurse towards the base case
}

Complexity. Time O(n): n + 1 calls of constant work each. Space O(n) for the call stack, because all frames are alive when the base case is reached.

Approach 3: Backtracking, recurse first then work

Intuition. Now suppose we are only allowed to count up in the parameter (start at 1, pass i + 1), but still want the output to come out decreasing. The trick is to move the work to after the recursive call. The call for i first lets the recursion handle i + 1 .. N, and only then appends i. The deepest call (i = N) finishes first and appends N; as the stack unwinds, N - 1, N - 2, …, 1 follow. The output is produced on the way up.

This is the backtracking shape: the recursion dives to the end and the useful work happens while returning. It is exactly the opposite pairing from the forward approach, which is why both versions produce the same descending output.

Algorithm.

  1. Start with backtrack(1, n, out).
  2. In backtrack(i, n, out): if i > n, return (base case).
  3. Otherwise call backtrack(i + 1, n, out) first, then append i.
static List<Integer> recursiveBacktrack(int n) {
    List<Integer> out = new ArrayList<>();
    backtrack(1, n, out);
    return out;
}

private static void backtrack(int i, int n, List<Integer> out) {
    if (i > n) return;          // base case
    backtrack(i + 1, n, out);   // recurse first ...
    out.add(i);                 // ... print on the way back, so n comes out first
}

Dry run on N = 3:

call work before recursing recursive call work after it returns
backtrack(1) none backtrack(2) append 1
backtrack(2) none backtrack(3) append 2
backtrack(3) none backtrack(4) append 3
backtrack(4) i > n, return    

The frames return in the order backtrack(3), backtrack(2), backtrack(1), so the appends happen as 3, 2, 1.

Complexity. Time O(n): n + 1 calls. Space O(n) for the call stack.

The two-by-two picture

Putting this problem next to printing 1 to N gives a small table worth memorising:

parameter moves work before the call work after the call
upward (1 → N) prints 1 .. N prints N .. 1
downward (N → 1) prints N .. 1 prints 1 .. N

“Work after the call” reverses the order in which the parameter visits the values. That single fact is behind reversing a linked list recursively, printing a path from a tree root after the recursion reaches a leaf, and many other patterns.

Edge cases and pitfalls