☕ DSA Java Articles

Topics › Basics › Learn Basic Recursion

Print name N times using recursion

Easy TUF ID 2405 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a string name and an integer N. Print name exactly N times, one per line, using recursion rather than a loop.

It is the natural follow-up to Understand recursion by print something N times: the text is now an input, so it has to travel through the recursion as a parameter, and we take the chance to look at two things the first exercise skipped, the cost of building strings by concatenation and how to keep the recursion depth small.

As in the previous article, the Java methods build the output into a String (each line terminated by \n) so that main can assert on it; printing that string gives the required output.

Constraints: 0 ≤ N ≤ 10^4 for the linear recursions; larger N is discussed in Approach 3.

Example 1

name = "Striver", N = 3
output:
Striver
Striver
Striver

Example 2

name = "Alice", N = 0
output: (nothing)

Baseline: the loop

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

Complexity. Time O(n · |name|) characters appended, space O(1) beyond the output. Every recursive version below is checked against this one.

Approach 1: The standard recursion

Intuition. Turn the loop counter into a parameter. The helper printName(i, n) means “print the name for lines i through n”. It prints one line and asks printName(i + 1, n) to print the remaining n - i lines. When i > n there is nothing to do, and the recursion stops. name and the output buffer are passed along unchanged so every frame can see them.

Algorithm.

  1. Call the helper with i = 1.
  2. In the helper: if i > n, return.
  3. Append name and a newline.
  4. Recurse with i + 1.
static String recursive(String name, int n) {
    StringBuilder out = new StringBuilder();
    printName(name, 1, n, out);
    return out.toString();
}

static void printName(String name, int i, int n, StringBuilder out) {
    if (i > n) return;                           // base case
    out.append(name).append('\n');               // print once
    printName(name, i + 1, n, out);              // let the next call handle the remaining n - i lines
}

Dry run for name = "Striver", n = 3:

call i > n? action
printName(1, 3) no append “Striver”, call printName(2, 3)
printName(2, 3) no append “Striver”, call printName(3, 3)
printName(3, 3) no append “Striver”, call printName(4, 3)
printName(4, 3) yes return; the three frames above then return in turn

Complexity. Time O(n) calls, each appending |name| characters. Space O(n) for the stack: when the base case runs, n + 1 frames are alive.

Why pass name to every call instead of reading a field? Because the function should depend only on its arguments; that is what makes recursive code easy to reason about and easy to test. The StringBuilder is passed for a different reason: appending to one shared buffer is far cheaper than creating a new string per level.

Approach 2: Build the answer by returning it

Intuition. Without a buffer, define the answer directly: the output for n lines is name + "\n" followed by the output for n - 1 lines, and the output for 0 lines is "". This is the recursive definition written down literally.

Algorithm.

  1. If n <= 0, return "".
  2. Return name + "\n" + (answer for n - 1).
static String recursiveReturn(String name, int n) {
    if (n <= 0) return "";
    return name + "\n" + recursiveReturn(name, n - 1);
}

Complexity. Time O(n^2 · |name|) characters copied: the deepest call returns 1 line, its caller copies that and adds one, and so on, so level k from the bottom copies about k lines. Space O(n) stack plus the intermediate strings.

This version is the clearest statement of the recursion, and the slowest. It is the right one to write on a whiteboard to explain the idea, and the wrong one to ship when n is large.

Approach 3: Divide and conquer, logarithmic depth

Intuition. Linear recursion uses one frame per line, so the stack depth equals n. We can do much better by splitting the work in half: n copies of a line are two blocks of n / 2 copies, plus one more copy when n is odd. Compute the half block once and use it twice. The depth is now the number of times n can be halved, about log2(n), and the total characters copied form a geometric series that sums to O(n · |name|), the same as the loop.

Algorithm.

  1. If n <= 0, return ""; if n == 1, return one line.
  2. half = answer for n / 2.
  3. If n is even return half + half, otherwise return half + half + one line.
static String recursiveHalving(String name, int n) {
    if (n <= 0) return "";
    if (n == 1) return name + "\n";
    String half = recursiveHalving(name, n / 2);
    return (n % 2 == 0) ? half + half : half + half + name + "\n";
}

Dry run for n = 7: half = f(3); f(3) needs f(1) = "name\n", and since 3 is odd returns f(1) + f(1) + line (3 lines); back at the top, 7 is odd, so the result is f(3) + f(3) + line, 3 + 3 + 1 = 7 lines. Only three frames were ever alive at once.

Complexity. Time O(n · |name|): the string built at each level is twice the size of the one below, so the top level dominates. Space O(log n) stack frames, plus the strings.

The tests build 200000 lines this way and compare the result with the loop. The linear versions would throw StackOverflowError long before that depth on a default JVM, which is exactly the point: when a recursion is naturally linear but must handle large inputs, look for a way to halve instead of decrement.

This is the same trick that turns the O(n) loop for x^n into O(log n) fast exponentiation, and the same reason merge sort has depth log n.

Edge cases and pitfalls