☕ DSA Java Articles

Topics › Basics › Learn Basic Recursion

Print 1 to N using Recursion

Easy TUF ID 850 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a positive integer N. Print the numbers 1, 2, 3, ..., N in increasing order without using a loop: the only tool allowed for repetition is recursion.

This is a warm-up for recursion, so the point is not the output (a for loop does it in one line) but the two different ways a recursive function can produce a sequence: doing the work before the recursive call, or after it. Both appear again and again in harder problems, so it is worth seeing them side by side on the simplest possible task.

Constraints: 1 ≤ N ≤ 10^4 in the usual statement. We also treat N ≤ 0 as “print nothing” so the base case is exercised.

To make the behaviour testable, the methods below collect the numbers into a List<Integer> instead of printing them. Replace out.add(x) with System.out.println(x) and you have the printing version.

Example 1

N = 5
output = 1 2 3 4 5        // every number from 1 up to N, each once, in order

Example 2

N = 1
output = 1                // a single number, the smallest non-trivial case

Example 3

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

Approach 1: The loop, as a reference

Intuition. Before replacing the loop, write it down so we know exactly what the recursion must reproduce: a counter i that starts at 1, emits itself, and advances to i + 1 until it passes N. Each recursive version below is a different way of simulating that counter with function calls.

Algorithm.

  1. Create an empty list.
  2. For i from 1 to N, append i.
  3. Return the list.
static List<Integer> iterative(int n) {
    List<Integer> out = new ArrayList<>();
    for (int i = 1; i <= n; 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. A loop keeps its state in the counter i. Recursion has no counter, but it has parameters: pass i as an argument and let each call represent one iteration. The call for i does the work for that iteration (emit i) and then asks the next call to handle i + 1. The chain stops when i exceeds N, which is exactly the loop’s exit condition turned into a base case.

The order of the two statements matters: because we emit before recursing, the numbers come out on the way down the call chain, so the first call prints 1, the second prints 2, and so on.

Algorithm.

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

private static void forward(int i, int n, List<Integer> out) {
    if (i > n) return;          // base case: nothing left to print
    out.add(i);                 // do the work ...
    forward(i + 1, n, out);     // ... then recurse
}

Complexity. Time O(n): exactly n + 1 calls, each doing constant work. Space O(n) for the call stack: all n frames are alive at once when the base case is reached, because no call returns until the one below it does.

Approach 3: Backtracking, recurse first then work

Intuition. Now flip the two statements. If the call for n first asks the recursion to handle 1 .. n - 1 and only then emits n, the output is still increasing: by the time we append n, everything smaller has already been appended by the calls deeper in the stack. The numbers come out on the way up, as the calls return. This “do the work while unwinding” shape is what people mean by backtracking in basic recursion.

Notice that this version needs no extra parameter: the problem for n is defined in terms of the problem for n - 1, which is the most natural recursive definition of “the list 1 to n” (it is “the list 1 to n - 1, followed by n”).

Algorithm.

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

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

Dry run on N = 3. Read the table top to bottom: calls go down until the base case, then the appends happen as each frame returns.

call action before recursing recursive call action after it returns
backtrack(3) none backtrack(2) append 3
backtrack(2) none backtrack(1) append 2
backtrack(1) none backtrack(0) append 1
backtrack(0) n < 1, return    

The appends execute in the order backtrack(1), backtrack(2), backtrack(3) finish, so the list becomes [1, 2, 3].

Complexity. Time O(n): n + 1 calls. Space O(n) for the call stack, same as Approach 2.

Which recursion shape should you reach for?

Both are correct here. In later problems (subsets, permutations, tree traversals) you will often need both at once: do something before the call, recurse, undo or record something after the call.

Edge cases and pitfalls