☕ DSA Java Articles

Topics › Basics › Learn Basic Recursion

Understand recursion by print something N times

Easy TUF ID 2401 A2Z

Java source ↗ Edit this article ↗

Problem

This is the first recursion exercise in the sheet, and it is deliberately tiny: print a fixed piece of text N times without a loop, using a function that calls itself. The real goal is to understand four things that every later recursive solution depends on:

  1. what a recursive call actually does to the program’s memory (the call stack),
  2. why every recursion needs a base case, and what happens without one,
  3. how a parameter that changes on each call makes the problem smaller,
  4. how the order of “do work” and “recurse” controls the order of the output.

To make the behaviour testable, the Java code builds the output into a String (one copy of the text per line) instead of printing directly; main asserts on that string and then prints it.

Constraints: 0 ≤ N ≤ 10^4 or so for the linear versions. Recursion depth is limited by the JVM stack, which is discussed below.

Example 1

text = "Hello", N = 3
output:
Hello
Hello
Hello

Example 2

text = "x", N = 0
output: (nothing)

What recursion is

A function is recursive when it calls itself. That alone would run forever, so a recursive function always has two parts:

For “print N times”, the smaller input is “print N - 1 times” and the base case is “print 0 times”, which means do nothing.

Each call occupies a stack frame holding its parameters and local variables. When f(1) calls f(2), f(1) is paused, not finished; it resumes only when f(2) returns. The frames pile up until the base case is hit, then unwind in reverse order. This is why a recursion of depth N uses O(N) memory even if each frame is tiny, and why a missing base case ends in StackOverflowError.

Baseline: the loop

For comparison, this is what we are replacing.

static String iterative(String text, int n) {
    StringBuilder out = new StringBuilder();
    for (int i = 1; i <= n; i++) out.append(text).append('\n');
    return out.toString();
}

Complexity. Time O(n), space O(1) beyond the output.

Approach 1: Recursion with a counter that goes up

Intuition. Mirror the loop exactly. The loop variable i becomes a parameter. The call countUp(i, n) means “print for the indices i, i+1, ..., n”. It prints once (for i) and delegates i+1..n to the next call. When i > n there is nothing left, which is the base case.

Algorithm.

  1. Start with i = 1.
  2. If i > n, return (base case).
  3. Append the text.
  4. Call yourself with i + 1.
static String recursiveCountUp(String text, int n) {
    StringBuilder out = new StringBuilder();
    countUp(text, 1, n, out);
    return out.toString();
}

static void countUp(String text, int i, int n, StringBuilder out) {
    if (i > n) return;                           // base case: nothing left to print
    out.append(text).append('\n');               // the work of this call
    countUp(text, i + 1, n, out);                // the same problem, one step smaller
}

Complexity. Time O(n), one call per line. Space O(n) for the call stack: all n + 1 frames are alive when the base case is reached, because every call is waiting for the one it made.

Note the pattern of a public wrapper plus a private helper with extra parameters. The caller should not have to know about i or the buffer; the wrapper supplies them.

Approach 2: Recursion with a counter that goes down

Intuition. Instead of counting from 1 to n, let the parameter itself be “how many lines are still to be printed”. countDown(n) prints one line and asks countDown(n - 1) for the rest; countDown(0) prints nothing. No separate index is needed, which is why most recursive definitions in mathematics are written this way (f(n) in terms of f(n - 1)).

Algorithm.

  1. If n <= 0, return.
  2. Append the text.
  3. Call yourself with n - 1.
static String recursiveCountDown(String text, int n) {
    StringBuilder out = new StringBuilder();
    countDown(text, n, out);
    return out.toString();
}

static void countDown(String text, int n, StringBuilder out) {
    if (n <= 0) return;
    out.append(text).append('\n');
    countDown(text, n - 1, out);
}

Complexity. Time O(n), space O(n) stack.

The base case is written n <= 0, not n == 0. With n == 0 a negative argument would never reach the base case and would recurse until the stack overflows. Writing base cases as inequalities is a cheap habit that prevents a whole class of bugs.

Approach 3: Returning the result instead of sharing a buffer

Intuition. The previous two versions pass a StringBuilder down and mutate it, which is the efficient choice. A purely functional recursion returns its answer instead: “the output for n is one line followed by the output for n - 1”. It has no helper and no shared state, which makes the structure of the recursion as visible as it gets.

Algorithm.

  1. If n <= 0, return the empty string.
  2. Return text + newline + (result for n - 1).
static String recursiveReturn(String text, int n) {
    if (n <= 0) return "";
    return text + "\n" + recursiveReturn(text, n - 1);
}

Complexity. Time O(n^2) characters copied in the worst case, because each level concatenates its line onto a string that grows with depth. Space O(n) stack plus the intermediate strings. Fine for understanding, wasteful for large n; prefer the buffer versions in real code.

Seeing the call stack

The helper below does no printing; it just logs when each call is entered and left. For n = 2 it produces

enter f(1)
enter f(2)
base case reached
leave f(2)
leave f(1)

static List<String> traceCalls(int n) {
    List<String> log = new ArrayList<>();
    trace(1, n, log);
    return log;
}

static void trace(int i, int n, List<String> log) {
    if (i > n) {
        log.add("base case reached");
        return;
    }
    log.add("enter f(" + i + ")");
    trace(i + 1, n, log);
    log.add("leave f(" + i + ")");
}

Read the log top to bottom: calls are entered in order 1, 2, and left in the reverse order 2, 1. Anything placed before the recursive call runs on the way down; anything placed after it runs on the way back up. Printing the text before the call (as all three approaches above do) gives the lines in forward order. Moving the print after the call would still produce n identical lines here, but as soon as the lines differ (printing i, for instance) the order flips. That single observation is the whole content of the next two problems in the sheet.

Edge cases and pitfalls