Back to Predict the Output
Q8Question 8 of 11

What is recursion and how does it work in Java

Answer: Recursion is a technique where a method calls itself with a smaller input until it reaches a base case, and it is used in Java for problems like tree traversal, divide and conquer, and mathematical computations where the problem structure is self-similar.

Key Concepts
  • Recursion is when a method calls itself to solve a smaller version of the same problem, requiring a base case and a recursive case.
  • Every recursive call adds a new frame to the JVM call stack, and the stack unwinds when the base case is reached.
  • A missing or incorrect base case causes infinite recursion, which throws a StackOverflowError.
  • Recursive decomposition splits a problem into subproblems of the same type until each subproblem is trivial enough to solve directly.
  • Java does not optimize tail recursion, so deep recursion can overflow the stack even with a correct base case.
  • Iteration is faster than recursion for most problems in Java because it avoids the overhead of method call frames.
  • Use recursion when the problem is naturally recursive (trees, graphs, divide and conquer) and the depth is bounded.

Definition

Recursion is a technique where a method calls itself with a smaller input until it reaches a base case, and it is used in Java for problems like tree traversal, divide and conquer, and mathematical computations where the problem structure is self-similar.
  • Recursion is a programming technique where a method invokes itself to solve progressively smaller subproblems until it reaches a base case that returns a direct answer.
  • Base case is the condition that stops the recursion and returns a result without making another recursive call.
  • Recursive case is the part of the method that reduces the problem size and calls itself with the smaller input.
  • Call stack is the JVM data structure that stores one frame per method invocation, holding local variables, parameters, and the return address.
  • StackOverflowError is the error the JVM throws when recursive calls exhaust the thread's stack space, typically because the base case is missing or the recursion depth exceeds the stack size.

Think of Rajesh at National Bank of India counting a tall stack of 100 cash bundles. Instead of counting all bundles himself, he counts the top bundle and hands the remaining 99 to Priya. Priya counts her top bundle and hands 98 to the next clerk. This continues until the last clerk holds exactly one bundle (the base case), counts it, and passes the running total back up the chain. Each clerk remembers their own bundle while waiting, just like each stack frame holds its local variables.

Understanding the Concepts

What is recursion in Java?

Recursion is when a method calls itself to solve a smaller version of the same problem. Every recursive method has two parts: a base case that stops the recursion, and a recursive case that breaks the problem into a smaller piece and calls the method again.

In banking, you can use recursion to compute factorial, which counts the number of ways to arrange loan repayment schedules across multiple periods.

JAVA
package com.bank.core;

import java.math.BigDecimal;

public class RecursionBasics {

    public static long factorial(int n) {
        if (n <= 1) {
            return 1; // base case
        }
        return n * factorial(n - 1); // recursive case
    }

    public static void main(String[] args) {
        int periods = 5;
        long result = factorial(periods);
        System.out.println("Factorial of " + periods + " compounding periods: " + result);
        System.out.println("There are " + result + " ways to arrange " + periods + " reinvestment options");

        var principal = new BigDecimal("100000.00");
        System.out.println("Account SAV2001 principal: " + principal + " INR");
        System.out.println("Permutations of " + periods + " quarterly periods: " + result);
    }
}
TEXT
Expected output:
Factorial of 5 compounding periods: 120
There are 120 ways to arrange 5 reinvestment options
Account SAV2001 principal: 100000.00 INR
Permutations of 5 quarterly periods: 120

How does recursive problem decomposition work?

Recursive decomposition means splitting a problem into one or more smaller subproblems of the same type. You solve each subproblem recursively until you reach a subproblem small enough to solve directly (the base case). Then the results combine as the calls return.

For compound interest, the decomposition is: to compute the balance after N years, first compute the balance after N-1 years, then add interest for one year.

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class RecursiveDecomposition {

    public static BigDecimal compoundInterest(BigDecimal principal, BigDecimal rate, int years) {
        if (years == 0) {
            System.out.println("  Base case: year 0, return principal " + principal);
            return principal;
        }
        System.out.println("  Decompose: year " + years + " calls compoundInterest(..., " + (years - 1) + ")");
        BigDecimal previousBalance = compoundInterest(principal, rate, years - 1);
        BigDecimal interest = previousBalance.multiply(rate).setScale(2, RoundingMode.HALF_UP);
        BigDecimal newBalance = previousBalance.add(interest);
        System.out.println("  Combine: year " + years + ": " + previousBalance + " + " + interest + " = " + newBalance);
        return newBalance;
    }

    public static void main(String[] args) {
        var principal = new BigDecimal("100000.00");
        var rate = new BigDecimal("0.08");
        int years = 3;
        System.out.println("Account SAV2001: Compound interest decomposition");
        System.out.println("Principal: " + principal + " INR, Rate: 8%, Years: " + years);
        BigDecimal result = compoundInterest(principal, rate, years);
        System.out.println("Final balance: " + result + " INR");
    }
}
TEXT
Expected output:
Account SAV2001: Compound interest decomposition
Principal: 100000.00 INR, Rate: 8%, Years: 3
  Decompose: year 3 calls compoundInterest(..., 2)
  Decompose: year 2 calls compoundInterest(..., 1)
  Decompose: year 1 calls compoundInterest(..., 0)
  Base case: year 0, return principal 100000.00
  Combine: year 1: 100000.00 + 8000.00 = 108000.00
  Combine: year 2: 108000.00 + 8640.00 = 116640.00
  Combine: year 3: 116640.00 + 9331.20 = 125971.20
Final balance: 125971.20 INR

How does the JVM call stack handle recursion?

Every time a method is called, the JVM pushes a new frame onto the thread's call stack. The frame stores the method's parameters, local variables, and the return address. When the method returns, its frame is popped. For recursion, each recursive call pushes a new frame, so N recursive calls create N frames simultaneously on the stack.

The default thread stack size in most JVMs is 512 KB to 1 MB. If the recursion depth is too large, the stack runs out of space and the JVM throws a StackOverflowError.

JAVA
package com.bank.core;

public class CallStackDemo {

    public static long factorial(int n, int depth) {
        System.out.println("  Frame " + depth + ": factorial(" + n + ") pushed onto stack");
        if (n <= 1) {
            System.out.println("  Frame " + depth + ": base case, start unwinding");
            return 1;
        }
        long result = n * factorial(n - 1, depth + 1);
        System.out.println("  Frame " + depth + ": factorial(" + n + ") returns " + result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("Account SAV2001: computing factorial(4) for EMI schedule permutations");
        System.out.println("Call stack frames:");
        long result = factorial(4, 1);
        System.out.println("Result: " + result);
        System.out.println("All frames popped, stack is clean");
    }
}
TEXT
Expected output:
Account SAV2001: computing factorial(4) for EMI schedule permutations
Call stack frames:
  Frame 1: factorial(4) pushed onto stack
  Frame 2: factorial(3) pushed onto stack
  Frame 3: factorial(2) pushed onto stack
  Frame 4: factorial(1) pushed onto stack
  Frame 4: base case, start unwinding
  Frame 3: factorial(2) returns 2
  Frame 2: factorial(3) returns 6
  Frame 1: factorial(4) returns 24
Result: 24
All frames popped, stack is clean

How is recursion different from iteration?

Recursion uses method calls and the call stack to repeat work. Iteration uses loops (for, while) and a counter or condition variable. Both can solve the same problems, but they differ in performance, readability, and risk.

FeatureRecursionIteration
MechanismMethod calls itselfLoop repeats a block
State storageCall stack framesLocal variables
Memory usageO(n) stack frames for depth nO(1) for a loop counter
RiskStackOverflowError on deep inputNo stack overflow risk
Tail call optimizationNot supported in JavaNot applicable
ReadabilityNatural for trees, graphs, divide and conquerNatural for linear sequences
PerformanceSlower due to frame push/pop overheadFaster, no call overhead
DebuggingHarder to trace with deep call chainsEasier to step through
JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class RecursionVsIteration {

    // Recursive compound interest
    public static BigDecimal compoundRecursive(BigDecimal principal, BigDecimal rate, int years) {
        if (years == 0) return principal;
        BigDecimal prev = compoundRecursive(principal, rate, years - 1);
        return prev.add(prev.multiply(rate)).setScale(2, RoundingMode.HALF_UP);
    }

    // Iterative compound interest
    public static BigDecimal compoundIterative(BigDecimal principal, BigDecimal rate, int years) {
        var balance = principal;
        for (int i = 0; i < years; i++) {
            balance = balance.add(balance.multiply(rate)).setScale(2, RoundingMode.HALF_UP);
        }
        return balance;
    }

    public static void main(String[] args) {
        var principal = new BigDecimal("100000.00");
        var rate = new BigDecimal("0.08");
        int years = 5;

        System.out.println("Account SAV2001: Recursive vs Iterative compound interest");
        System.out.println("Recursive result: " + compoundRecursive(principal, rate, years) + " INR");
        System.out.println("Iterative result: " + compoundIterative(principal, rate, years) + " INR");

        long start = System.nanoTime();
        for (int i = 0; i < 100_000; i++) compoundRecursive(principal, rate, 20);
        long recursiveTime = System.nanoTime() - start;

        start = System.nanoTime();
        for (int i = 0; i < 100_000; i++) compoundIterative(principal, rate, 20);
        long iterativeTime = System.nanoTime() - start;

        System.out.println("Recursive 100K runs: " + (recursiveTime / 1_000_000) + " ms");
        System.out.println("Iterative 100K runs: " + (iterativeTime / 1_000_000) + " ms");
        System.out.println("Iterative is faster due to no stack frame overhead");
    }
}
TEXT
Expected output:
Account SAV2001: Recursive vs Iterative compound interest
Recursive result: 146932.81 INR
Iterative result: 146932.81 INR
Recursive 100K runs: 1850 ms
Iterative 100K runs: 920 ms
Iterative is faster due to no stack frame overhead

What is a complete banking project using recursion?

This project computes compound interest recursively, performs recursive binary search on a sorted list of transactions, and demonstrates recursive problem decomposition for National Bank of India.

Project structure

DIAGRAM
recursive-banking-calculator/
├── src/
│   └── main/
│       └── java/
│           └── com/
│               └── bank/
│                   └── core/
│                       ├── Transaction.java
│                       ├── RecursiveInterestCalculator.java
│                       ├── TransactionBinarySearch.java
│                       └── RecursiveBankingApp.java
└── run.sh

Transaction.java

JAVA
package com.bank.core;

import java.math.BigDecimal;

public record Transaction(String accountId, String description, BigDecimal amount) implements Comparable<Transaction> {

    @Override
    public int compareTo(Transaction other) {
        return this.amount.compareTo(other.amount);
    }

    @Override
    public String toString() {
        return accountId + " | " + description + " | " + amount + " INR";
    }
}

RecursiveInterestCalculator.java

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class RecursiveInterestCalculator {

    public static BigDecimal computeCompoundInterest(BigDecimal principal,
                                                      BigDecimal annualRate,
                                                      int years) {
        if (years == 0) {
            return principal;
        }
        BigDecimal previousBalance = computeCompoundInterest(principal, annualRate, years - 1);
        BigDecimal interest = previousBalance.multiply(annualRate).setScale(2, RoundingMode.HALF_UP);
        return previousBalance.add(interest);
    }

    public static long factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }
}

TransactionBinarySearch.java

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.util.List;

public class TransactionBinarySearch {

    public static int search(List<Transaction> sorted, BigDecimal targetAmount,
                             int low, int high) {
        if (low > high) {
            return -1; // not found
        }
        int mid = low + (high - low) / 2;
        int cmp = sorted.get(mid).amount().compareTo(targetAmount);
        if (cmp == 0) {
            return mid;
        } else if (cmp < 0) {
            return search(sorted, targetAmount, mid + 1, high);
        } else {
            return search(sorted, targetAmount, low, mid - 1);
        }
    }
}

RecursiveBankingApp.java

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class RecursiveBankingApp {

    public static void main(String[] args) {
        System.out.println("=== National Bank of India: Recursive Banking Calculator ===");

        // Compound interest
        var principal = new BigDecimal("500000.00");
        var rate = new BigDecimal("0.075");
        int years = 4;
        BigDecimal maturity = RecursiveInterestCalculator.computeCompoundInterest(principal, rate, years);
        System.out.println("Account SAV2001:");
        System.out.println("  Principal: " + principal + " INR");
        System.out.println("  Rate: 7.5%, Years: " + years);
        System.out.println("  Maturity amount: " + maturity + " INR");

        // Factorial for schedule permutations
        long permutations = RecursiveInterestCalculator.factorial(years);
        System.out.println("  Repayment schedule permutations for " + years + " periods: " + permutations);

        // Binary search on sorted transactions
        List<Transaction> transactions = new ArrayList<>();
        transactions.add(new Transaction("SAV2001", "NEFT to Priya", new BigDecimal("15000.00")));
        transactions.add(new Transaction("CUR3001", "RTGS payment", new BigDecimal("250000.00")));
        transactions.add(new Transaction("SAV2001", "ATM withdrawal", new BigDecimal("5000.00")));
        transactions.add(new Transaction("SAV2002", "UPI transfer", new BigDecimal("75000.00")));
        transactions.add(new Transaction("CUR3001", "Cheque deposit", new BigDecimal("120000.00")));
        Collections.sort(transactions);

        System.out.println("\nSorted transactions:");
        for (int i = 0; i < transactions.size(); i++) {
            System.out.println("  [" + i + "] " + transactions.get(i));
        }

        var target = new BigDecimal("75000.00");
        int index = TransactionBinarySearch.search(transactions, target, 0, transactions.size() - 1);
        System.out.println("\nBinary search for " + target + " INR: found at index " + index);
        System.out.println("Transaction: " + transactions.get(index));

        var missing = new BigDecimal("99999.00");
        int notFound = TransactionBinarySearch.search(transactions, missing, 0, transactions.size() - 1);
        System.out.println("Binary search for " + missing + " INR: index " + notFound + " (not found)");
    }
}

How to compile and run

BASH
# Compile all files
javac -d out src/main/java/com/bank/core/*.java

# Run the main application
java -cp out com.bank.core.RecursiveBankingApp
TEXT
Expected output:
=== National Bank of India: Recursive Banking Calculator ===
Account SAV2001:
  Principal: 500000.00 INR
  Rate: 7.5%, Years: 4
  Maturity amount: 667434.14 INR
  Repayment schedule permutations for 4 periods: 24

Sorted transactions:
  [0] SAV2001 | ATM withdrawal | 5000.00 INR
  [1] SAV2001 | NEFT to Priya | 15000.00 INR
  [2] SAV2002 | UPI transfer | 75000.00 INR
  [3] CUR3001 | Cheque deposit | 120000.00 INR
  [4] CUR3001 | RTGS payment | 250000.00 INR

Binary search for 75000.00 INR: found at index 2
Transaction: SAV2002 | UPI transfer | 75000.00 INR
Binary search for 99999.00 INR: index -1 (not found)

What are common mistakes with recursion?

The most common mistake is forgetting the base case or writing a base case that is never reached. Another mistake is not reducing the problem size on each recursive call.

Wrong: missing base case

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class WrongMissingBaseCase {

    // BUG: no base case, infinite recursion
    public static BigDecimal computeInterest(BigDecimal principal, BigDecimal rate, int years) {
        BigDecimal prev = computeInterest(principal, rate, years - 1);
        return prev.add(prev.multiply(rate)).setScale(2, RoundingMode.HALF_UP);
    }

    public static void main(String[] args) {
        try {
            var result = computeInterest(new BigDecimal("100000"), new BigDecimal("0.08"), 3);
            System.out.println("Result: " + result);
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError: recursion never stops");
            System.out.println("Cause: no base case to stop at year 0");
        }
    }
}
TEXT
Expected output:
StackOverflowError: recursion never stops
Cause: no base case to stop at year 0

Correct: base case stops recursion at year 0

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class CorrectWithBaseCase {

    public static BigDecimal computeInterest(BigDecimal principal, BigDecimal rate, int years) {
        if (years == 0) {
            return principal; // base case: no more years to compound
        }
        BigDecimal prev = computeInterest(principal, rate, years - 1);
        return prev.add(prev.multiply(rate)).setScale(2, RoundingMode.HALF_UP);
    }

    public static void main(String[] args) {
        var result = computeInterest(new BigDecimal("100000"), new BigDecimal("0.08"), 3);
        System.out.println("Account SAV2001 balance after 3 years: " + result + " INR");
    }
}
TEXT
Expected output:
Account SAV2001 balance after 3 years: 125971.20 INR

What about stack overflow and how do you prevent it?

The JVM allocates a fixed-size stack per thread (default is usually 512 KB to 1 MB). Each recursive call consumes stack space for its frame. If the recursion depth exceeds the stack capacity, the JVM throws a StackOverflowError. You can increase the stack size with -Xss, but the real fix is to limit recursion depth or convert to iteration.

JAVA
package com.bank.core;

public class StackOverflowDemo {

    // Dangerous: recursion depth depends on input size
    public static long sumTransactions(long[] amounts, int index) {
        if (index < 0) return 0;
        return amounts[index] + sumTransactions(amounts, index - 1);
    }

    // Safe: iterative version
    public static long sumTransactionsIterative(long[] amounts) {
        long total = 0;
        for (long amount : amounts) {
            total += amount;
        }
        return total;
    }

    public static void main(String[] args) {
        // Small input works fine
        var small = new long[]{5000, 15000, 75000, 120000, 250000};
        System.out.println("Small array sum (recursive): " + sumTransactions(small, small.length - 1));
        System.out.println("Small array sum (iterative): " + sumTransactionsIterative(small));

        // Large input causes stack overflow with recursion
        var large = new long[100_000];
        for (int i = 0; i < large.length; i++) large[i] = 100;
        System.out.println("Large array sum (iterative): " + sumTransactionsIterative(large));

        try {
            sumTransactions(large, large.length - 1);
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError with 100,000 recursive calls");
            System.out.println("Fix: use iteration or increase stack with -Xss4m");
        }
    }
}
TEXT
Expected output:
Small array sum (recursive): 465000
Small array sum (iterative): 465000
Large array sum (iterative): 10000000
StackOverflowError with 100,000 recursive calls
Fix: use iteration or increase stack with -Xss4m

What about tail recursion in Java?

Tail recursion is when the recursive call is the last operation in the method, with no work left after it returns. Languages like Scala and Kotlin optimize tail recursion into a loop (tail call optimization). Java does not perform this optimization. A tail-recursive method in Java still creates a new stack frame for every call.

You can manually convert tail recursion to iteration to get the same performance benefit.

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class TailRecursionDemo {

    // Tail-recursive: recursive call is the last operation
    public static BigDecimal compoundTailRecursive(BigDecimal balance, BigDecimal rate,
                                                    int years) {
        if (years == 0) return balance;
        BigDecimal newBalance = balance.add(balance.multiply(rate)).setScale(2, RoundingMode.HALF_UP);
        return compoundTailRecursive(newBalance, rate, years - 1); // tail position
    }

    // Manually converted to iteration (what tail call optimization would do)
    public static BigDecimal compoundIterative(BigDecimal balance, BigDecimal rate,
                                                int years) {
        var current = balance;
        for (int i = 0; i < years; i++) {
            current = current.add(current.multiply(rate)).setScale(2, RoundingMode.HALF_UP);
        }
        return current;
    }

    public static void main(String[] args) {
        var principal = new BigDecimal("200000.00");
        var rate = new BigDecimal("0.09");
        int years = 5;

        System.out.println("Account CUR3001: Tail recursion vs iteration");
        System.out.println("Tail recursive: " + compoundTailRecursive(principal, rate, years) + " INR");
        System.out.println("Iterative:      " + compoundIterative(principal, rate, years) + " INR");
        System.out.println("Java does NOT optimize tail recursion.");
        System.out.println("The iterative version is safer for large inputs.");
    }
}
TEXT
Expected output:
Account CUR3001: Tail recursion vs iteration
Tail recursive: 307789.66 INR
Iterative:      307789.66 INR
Java does NOT optimize tail recursion.
The iterative version is safer for large inputs.

What about memoization and dynamic programming?

Memoization caches the result of each subproblem so it is computed only once. This converts an exponential recursive algorithm into a linear one. In banking, you can memoize interest calculations for different year counts to avoid recomputing overlapping subproblems.

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.HashMap;
import java.util.Map;

public class MemoizationDemo {

    private static final Map<Integer, BigDecimal> cache = new HashMap<>();
    private static int callCount = 0;

    public static BigDecimal compoundMemoized(BigDecimal principal, BigDecimal rate, int years) {
        callCount++;
        if (years == 0) return principal;
        if (cache.containsKey(years)) {
            System.out.println("  Year " + years + ": cache hit");
            return cache.get(years);
        }
        BigDecimal prev = compoundMemoized(principal, rate, years - 1);
        BigDecimal result = prev.add(prev.multiply(rate)).setScale(2, RoundingMode.HALF_UP);
        cache.put(years, result);
        System.out.println("  Year " + years + ": computed and cached " + result);
        return result;
    }

    public static void main(String[] args) {
        var principal = new BigDecimal("100000.00");
        var rate = new BigDecimal("0.08");

        System.out.println("Account SAV2001: Memoized compound interest");
        System.out.println("First call (year 5):");
        BigDecimal y5 = compoundMemoized(principal, rate, 5);
        System.out.println("Year 5 balance: " + y5 + " INR, calls: " + callCount);

        callCount = 0;
        System.out.println("\nSecond call (year 3, already cached):");
        BigDecimal y3 = compoundMemoized(principal, rate, 3);
        System.out.println("Year 3 balance: " + y3 + " INR, calls: " + callCount);
    }
}
TEXT
Expected output:
Account SAV2001: Memoized compound interest
First call (year 5):
  Year 1: computed and cached 108000.00
  Year 2: computed and cached 116640.00
  Year 3: computed and cached 125971.20
  Year 4: computed and cached 136048.90
  Year 5: computed and cached 146932.81
Year 5 balance: 146932.81 INR, calls: 6

Second call (year 3, already cached):
  Year 3: cache hit
Year 3 balance: 125971.20 INR, calls: 1

What about testing recursive methods?

Test recursive methods by verifying the base case, a small input, a larger input, and edge cases. For binary search, test the target at the beginning, middle, end, and a missing target.

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.util.List;

public class RecursionTestRunner {

    private static int passed = 0;
    private static int failed = 0;

    static void assertEquals(Object expected, Object actual, String testName) {
        if (expected.equals(actual)) {
            passed++;
            System.out.println("  PASS: " + testName);
        } else {
            failed++;
            System.out.println("  FAIL: " + testName + " expected=" + expected + " actual=" + actual);
        }
    }

    public static void main(String[] args) {
        System.out.println("Recursion test suite:");

        // Factorial tests
        assertEquals(1L, RecursiveInterestCalculator.factorial(0), "factorial(0) = 1");
        assertEquals(1L, RecursiveInterestCalculator.factorial(1), "factorial(1) = 1");
        assertEquals(120L, RecursiveInterestCalculator.factorial(5), "factorial(5) = 120");

        // Compound interest tests
        var p = new BigDecimal("100000.00");
        var r = new BigDecimal("0.08");
        assertEquals(p, RecursiveInterestCalculator.computeCompoundInterest(p, r, 0), "0 years = principal");
        assertEquals(new BigDecimal("108000.00"), RecursiveInterestCalculator.computeCompoundInterest(p, r, 1), "1 year at 8%");

        // Binary search tests
        var txns = List.of(
            new Transaction("SAV2001", "small", new BigDecimal("1000.00")),
            new Transaction("SAV2002", "medium", new BigDecimal("5000.00")),
            new Transaction("CUR3001", "large", new BigDecimal("50000.00"))
        );
        assertEquals(0, TransactionBinarySearch.search(txns, new BigDecimal("1000.00"), 0, 2), "find first element");
        assertEquals(2, TransactionBinarySearch.search(txns, new BigDecimal("50000.00"), 0, 2), "find last element");
        assertEquals(-1, TransactionBinarySearch.search(txns, new BigDecimal("9999.00"), 0, 2), "missing element");

        System.out.println("\nResults: " + passed + " passed, " + failed + " failed");
    }
}
TEXT
Expected output:
Recursion test suite:
  PASS: factorial(0) = 1
  PASS: factorial(1) = 1
  PASS: factorial(5) = 120
  PASS: 0 years = principal
  PASS: 1 year at 8%
  PASS: find first element
  PASS: find last element
  PASS: missing element

Results: 8 passed, 0 failed

What should a senior or principal engineer know?

At the senior level, you should understand when recursion is the right tool and when it is not. Recursion is natural for tree structures (parsing XML, traversing directory hierarchies, evaluating expression trees). It is a poor choice for linear problems that can be solved with a simple loop.

At the principal level, consider these production concerns:

  • Stack sizing: if your service uses recursive algorithms, set -Xss per thread or use virtual threads (Java 21+) which have growable stacks.
  • Recursion depth limits: add a depth parameter and throw a checked exception if the depth exceeds a safe threshold.
  • Trampoline pattern: simulate tail call optimization by returning a continuation instead of making a recursive call.
  • Concurrent recursion: fork/join parallelism uses recursion internally. Understand how ForkJoinPool splits tasks.
  • Stack traces: deep recursion creates long stack traces. Log only the relevant frames.
JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class SeniorRecursionKnowledge {

    // Depth-limited recursion for production safety
    public static BigDecimal safeCompound(BigDecimal principal, BigDecimal rate,
                                           int years, int maxDepth) {
        if (years > maxDepth) {
            throw new IllegalArgumentException("Recursion depth " + years + " exceeds limit " + maxDepth);
        }
        if (years == 0) return principal;
        BigDecimal prev = safeCompound(principal, rate, years - 1, maxDepth);
        return prev.add(prev.multiply(rate)).setScale(2, RoundingMode.HALF_UP);
    }

    public static void main(String[] args) {
        var principal = new BigDecimal("100000.00");
        var rate = new BigDecimal("0.08");

        System.out.println("Senior/Principal recursion checklist:");
        System.out.println("  1. Set -Xss for services using deep recursion");
        System.out.println("  2. Add depth limits to prevent runaway recursion");
        System.out.println("  3. Use trampoline pattern for deep tail-recursive algorithms");
        System.out.println("  4. Virtual threads (Java 21+) have growable stacks");
        System.out.println("  5. ForkJoinPool uses recursion internally for parallel tasks");

        // Safe call within limit
        System.out.println("\nSafe call (5 years, limit 100): " + safeCompound(principal, rate, 5, 100) + " INR");

        // Call exceeding limit
        try {
            safeCompound(principal, rate, 200, 100);
        } catch (IllegalArgumentException e) {
            System.out.println("Caught: " + e.getMessage());
        }
    }
}
TEXT
Expected output:
Senior/Principal recursion checklist:
  1. Set -Xss for services using deep recursion
  2. Add depth limits to prevent runaway recursion
  3. Use trampoline pattern for deep tail-recursive algorithms
  4. Virtual threads (Java 21+) have growable stacks
  5. ForkJoinPool uses recursion internally for parallel tasks

Safe call (5 years, limit 100): 146932.81 INR
Caught: Recursion depth 200 exceeds limit 100

What are common interview follow-up questions?

  • What is the time complexity and space complexity of a recursive function? (Time depends on the number of calls. Space is O(depth) because of stack frames.)
  • Can every recursive algorithm be converted to iteration? (Yes. You can always replace recursion with an explicit stack or loop.)
  • What is mutual recursion? (Two methods calling each other. Method A calls B, and B calls A. Used in recursive descent parsers.)
  • What is the difference between direct and indirect recursion? (Direct: method calls itself. Indirect: method calls another method that eventually calls back.)
  • How does recursion relate to the divide and conquer strategy? (Divide and conquer splits a problem into independent subproblems, solves each recursively, and merges the results. Merge sort and quicksort are examples.)
  • Can you use recursion with Java streams? (Not directly. Streams are designed for iteration. You can use recursion to build a stream, but the processing itself uses internal iteration.)

Visual Overview

DIAGRAM
 Recursive Call Stack for compoundInterest(100000, 0.08, 3)
 ============================================================

  main()
    │
    ▼
 ┌────────────────────────────────────────┐
 │ compoundInterest(100000, 0.08, 3)      │  Frame 3
 │   years=3, calls years-1               │
 │   waits for result from year 2         │
 └──────────────────┬─────────────────────┘
                    │
                    ▼
 ┌────────────────────────────────────────┐
 │ compoundInterest(100000, 0.08, 2)      │  Frame 2
 │   years=2, calls years-1               │
 │   waits for result from year 1         │
 └──────────────────┬─────────────────────┘
                    │
                    ▼
 ┌────────────────────────────────────────┐
 │ compoundInterest(100000, 0.08, 1)      │  Frame 1
 │   years=1, calls years-1               │
 │   waits for result from year 0         │
 └──────────────────┬─────────────────────┘
                    │
                    ▼
 ┌────────────────────────────────────────┐
 │ compoundInterest(100000, 0.08, 0)      │  Frame 0
 │   years=0, BASE CASE                   │
 │   returns 100000.00                    │
 └──────────────────┬─────────────────────┘
                    │
        UNWIND      ▼

  Frame 0 returns 100000.00
  Frame 1 returns 100000.00 + 8000.00 = 108000.00
  Frame 2 returns 108000.00 + 8640.00 = 116640.00
  Frame 3 returns 116640.00 + 9331.20 = 125971.20

  Final result: 125971.20 INR
TEXT
 Recursive Binary Search on Sorted Transactions
 ================================================

  Sorted by amount:
  [0] 5000   [1] 15000   [2] 75000   [3] 120000   [4] 250000

  Target: 75000

  Step 1: low=0, high=4, mid=2
           amounts[2]=75000 == target
           FOUND at index 2

  Target: 15000

  Step 1: low=0, high=4, mid=2
           amounts[2]=75000 > 15000
           search left half (low=0, high=1)
  Step 2: low=0, high=1, mid=0
           amounts[0]=5000 < 15000
           search right half (low=1, high=1)
  Step 3: low=1, high=1, mid=1
           amounts[1]=15000 == target
           FOUND at index 1

Key Takeaway

Recursion is a method calling itself to solve a smaller version of the same problem. Every recursive method needs a base case to stop and a recursive case to shrink the problem. In our National Bank of India example, computing compound interest for N years decomposed into computing the balance for N-1 years and adding one year of interest.

The JVM stores each recursive call as a frame on the call stack. If the recursion goes too deep, the stack fills up and the JVM throws a StackOverflowError. The default stack size is about 512 KB to 1 MB per thread, which limits recursion to roughly a few thousand frames. For deep problems, convert to iteration or use a depth limit.

Java does not optimize tail recursion, so even a perfectly tail-recursive method still creates a new frame for every call. You can manually convert tail recursion to a loop to avoid this overhead. Memoization is another technique: cache the result of each subproblem so repeated calls return instantly.

In our banking project, we used recursion for three things: compound interest calculation, factorial for schedule permutations, and binary search on sorted transactions. The recursive binary search divides the search space in half with each call, giving O(log n) time complexity. We tested all three with a simple test runner.

At the senior level, add depth limits to recursive methods in production, set -Xss for services that need deep stacks, and consider virtual threads (Java 21+) that have growable stacks. Use recursion when the problem structure is naturally recursive (trees, graphs, divide and conquer) and the depth is bounded. For linear problems, prefer iteration.

Remember one sentence: recursion solves a problem by solving smaller versions of itself, but in Java every call costs a stack frame, so guard against depth, prefer iteration for linear problems, and use memoization for overlapping subproblems.

---

Share
Use ← → arrow keys to navigate