Definition
Recursion has two essential parts that every correct implementation must include.
- Base case is the condition where the method returns a direct answer without calling itself, which stops the chain.
- Recursive case is the step where the method reduces the problem and calls itself on the smaller input.
- Call stack stores a new frame for each recursive call, holding local variables and the return address.
- Unwinding happens when the base case returns and the frames pop off one by one, combining results on the way back up.
- Termination guarantee comes from shrinking the input on every call so the base case is always reached.
Imagine Rajesh at National Bank of India wants to know the total balance across a chain of linked savings accounts, where each account points to the next one. Instead of writing one giant loop, he asks: what is my balance plus the total of the rest of the chain? To find the total of the rest, he asks the exact same question about the next account. This keeps going until he reaches the last account that points to nothing, and then the answers add back up the chain.
Understanding the Concepts
What is Recursion?
Recursion is a technique where a method solves a problem by calling itself on a smaller version of the same problem. Every correct recursive method has two parts: a base case that returns a direct answer without recursing and a recursive case that reduces the problem and calls the method again. Each call gets its own stack frame on the call stack, and the frames unwind as the base case is reached.
At National Bank of India, Rajesh uses recursion to walk a chain of linked savings accounts and compute the combined balance.
package com.bank.core;
import java.math.BigDecimal;
public class AccountChain {
private BigDecimal balance;
private AccountChain next;
public AccountChain(BigDecimal balance, AccountChain next) {
this.balance = balance;
this.next = next;
}
public static BigDecimal totalBalance(AccountChain account) {
// Base case: end of chain
if (account == null) {
return BigDecimal.ZERO;
}
// Recursive case: this balance + total of the rest
return account.balance.add(totalBalance(account.next));
}
public static void main(String[] args) {
AccountChain chain = new AccountChain(new BigDecimal("50000.00"),
new AccountChain(new BigDecimal("75000.00"),
new AccountChain(new BigDecimal("30000.00"), null)));
System.out.println("Total balance: " + totalBalance(chain));
}
}
Total balance: 155000.00
Why Does Recursion Exist?
Recursion exists because many problems are naturally self-similar. A linked list is a node followed by a smaller linked list. A tree is a root connected to smaller trees. A sorted array can be halved into two smaller sorted arrays. When the structure of the data is recursive, writing a recursive solution maps directly to the structure and produces cleaner code than an iterative version.
At National Bank of India, the organizational hierarchy is a tree where each branch manager oversees smaller teams. Computing the total headcount under any manager is natural with recursion.
package com.bank.service;
import java.util.List;
import java.util.ArrayList;
public class OrgNode {
String name;
List<OrgNode> reports = new ArrayList<>();
public OrgNode(String name) { this.name = name; }
public static int headcount(OrgNode manager) {
if (manager == null) return 0;
int count = 1; // count the manager
for (OrgNode report : manager.reports) {
count += headcount(report);
}
return count;
}
}
How Does Recursion Work Internally?
Every time a method calls itself, the JVM pushes a new frame onto the call stack. That frame stores the local variables, the parameters, and the address to return to when the call finishes. As the recursion goes deeper, more frames pile up. When the base case finally returns, the frames pop off one by one and each caller receives the result from its callee.
The call stack for totalBalance with three accounts looks like this during execution:
package com.bank.core;
import java.math.BigDecimal;
public class StackDemo {
public static BigDecimal totalBalance(String label, BigDecimal balance, int depth) {
String indent = " ".repeat(depth);
System.out.println(indent + "PUSH frame: " + label + " balance=" + balance);
if (balance == null) {
System.out.println(indent + "BASE CASE: return 0");
return BigDecimal.ZERO;
}
// Simulate next account
BigDecimal rest = (depth < 2)
? totalBalance("Account" + (depth + 2), new BigDecimal("10000"), depth + 1)
: totalBalance("null", null, depth + 1);
BigDecimal result = balance.add(rest);
System.out.println(indent + "POP frame: " + label + " returns " + result);
return result;
}
public static void main(String[] args) {
totalBalance("Account1", new BigDecimal("50000"), 0);
}
}
PUSH frame: Account1 balance=50000
PUSH frame: Account2 balance=10000
PUSH frame: Account3 balance=10000
PUSH frame: null balance=null
BASE CASE: return 0
POP frame: Account3 returns 10000
POP frame: Account2 returns 20000
POP frame: Account1 returns 70000
How Is Recursion Different from Iteration?
Recursion and iteration can both solve repetitive problems, but they differ in mechanism and suitability.
| Aspect | Recursion | Iteration |
|---|---|---|
| Mechanism | Method calls itself | Loop repeats a block |
| State storage | Each call gets a stack frame | Variables in the loop body |
| Memory | O(n) stack frames for depth n | O(1) extra memory |
| Overflow risk | StackOverflowError on deep input | No overflow risk |
| Code clarity | Matches self-similar structures | Better for flat sequences |
| JVM optimization | No tail-call optimization | Naturally efficient |
Here is the same account-chain total written iteratively:
package com.bank.core;
import java.math.BigDecimal;
public class IterativeTotal {
public static BigDecimal totalBalance(AccountChain account) {
BigDecimal sum = BigDecimal.ZERO;
AccountChain current = account;
while (current != null) {
sum = sum.add(current.getBalance());
current = current.getNext();
}
return sum;
}
}
What Are the Rules for Writing Correct Recursion?
Every recursive method must follow three rules to work correctly.
First, define a base case that returns without recursing. Without it the method calls itself forever. Second, ensure the recursive case reduces the problem toward the base case on every call. If the input does not shrink, the base case is never reached. Third, do not modify shared mutable state between calls unless you explicitly manage it, because each frame sees its own locals but shares heap objects.
package com.bank.service;
import java.math.BigDecimal;
public class InterestCalculator {
// Computes compound interest for n periods recursively
public static BigDecimal compoundInterest(BigDecimal principal, BigDecimal rate, int periods) {
// Rule 1: base case
if (periods == 0) {
return principal;
}
// Rule 2: reduce toward base case (periods - 1)
BigDecimal grown = principal.multiply(BigDecimal.ONE.add(rate));
return compoundInterest(grown, rate, periods - 1);
}
public static void main(String[] args) {
BigDecimal result = compoundInterest(
new BigDecimal("100000"), new BigDecimal("0.08"), 5);
System.out.println("Amount after 5 years: " + result.setScale(2, java.math.RoundingMode.HALF_UP));
}
}
Amount after 5 years: 146932.81
What Exceptions Can Occur?
The most common exception in recursion is StackOverflowError. It occurs when the recursion goes too deep and the call stack runs out of space. The default stack size in the JVM is typically 512 KB to 1 MB, which allows roughly a few thousand frames.
Here is code that triggers the error:
package com.bank.core;
public class StackOverflowDemo {
// Missing proper base case: will overflow
public static int badSum(int n) {
return n + badSum(n - 1); // no base case!
}
// Correct version with base case
public static int goodSum(int n) {
if (n <= 0) return 0; // base case stops recursion
return n + goodSum(n - 1);
}
public static void main(String[] args) {
try {
badSum(10);
} catch (StackOverflowError e) {
System.out.println("StackOverflowError: recursion never stops");
}
System.out.println("Good sum of 10: " + goodSum(10));
}
}
StackOverflowError: recursion never stops
Good sum of 10: 55
What Are Common Mistakes?
The first common mistake is forgetting the base case entirely. The second is writing a base case that the recursive case never reaches. The third is not reducing the problem, so the same input repeats forever.
Wrong code where the problem does not shrink:
// WRONG: passes the same list, never shrinks
public static BigDecimal totalWrong(List<BigDecimal> balances, int index) {
if (index >= balances.size()) return BigDecimal.ZERO;
return balances.get(index).add(totalWrong(balances, index)); // BUG: index not incremented
}
Correct code:
// CORRECT: index increments toward the base case
public static BigDecimal totalCorrect(List<BigDecimal> balances, int index) {
if (index >= balances.size()) return BigDecimal.ZERO;
return balances.get(index).add(totalCorrect(balances, index + 1)); // index + 1 shrinks problem
}
What About Tail Recursion and JVM Optimization?
Tail recursion is when the recursive call is the very last operation in the method, meaning no work is done after the call returns. Some languages like Scala and Kotlin on the JVM optimize tail recursion into a loop so the stack does not grow. The standard Java compiler and JVM do not perform this optimization.
This means that for deep recursion problems in Java, you should convert the recursion to an explicit loop or use an explicit stack data structure.
package com.bank.service;
import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.Deque;
public class ExplicitStackTotal {
// Using an explicit stack instead of recursion
public static BigDecimal totalWithStack(AccountChain head) {
Deque<AccountChain> stack = new ArrayDeque<>();
AccountChain current = head;
while (current != null) {
stack.push(current);
current = current.getNext();
}
BigDecimal sum = BigDecimal.ZERO;
while (!stack.isEmpty()) {
sum = sum.add(stack.pop().getBalance());
}
return sum;
}
}
When Should You Use Recursion?
Use recursion when the data structure is naturally self-similar: trees, linked lists, graphs, and divide-and-conquer problems. Use iteration when the problem is a flat sequence, when the depth could be very large, or when performance and memory matter more than code clarity.
At National Bank of India, Rajesh uses recursion for traversing the organizational tree, for walking nested JSON in API responses, and for divide-and-conquer sorting of transaction batches. He uses iteration for scanning flat lists of transactions, computing running balances, and processing sequential queue items.
package com.bank.service;
import java.util.List;
public class RecursionGuideline {
// Good use of recursion: tree traversal
public static void printOrgTree(OrgNode node, int depth) {
if (node == null) return;
System.out.println(" ".repeat(depth) + node.name);
for (OrgNode child : node.reports) {
printOrgTree(child, depth + 1);
}
}
// Bad use of recursion: flat list sum (use a loop instead)
public static long sumList(List<Long> amounts, int i) {
if (i >= amounts.size()) return 0;
return amounts.get(i) + sumList(amounts, i + 1);
}
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly follow up with these questions after discussing recursion:
- Convert a recursive solution to iterative. This tests whether you understand that the call stack can be replaced by an explicit stack or loop.
- Identify the time and space complexity of a recursive method. The space is at least O(depth) because of the stack frames.
- Explain memoization. This is caching the results of recursive calls to avoid recomputing overlapping subproblems.
- Write a recursive solution for factorial, Fibonacci, or binary search. These are the standard warm-up problems.
package com.bank.core;
public class RecursionClassics {
// Factorial: base case is 0! = 1
public static long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
// Fibonacci with memoization
public static long fib(int n, long[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
public static void main(String[] args) {
System.out.println("5! = " + factorial(5));
System.out.println("fib(10) = " + fib(10, new long[11]));
}
}
5! = 120
fib(10) = 55
Visual Overview
totalBalance(Account1)
│
├─ balance = 50000
├─ calls totalBalance(Account2)
│ │
│ ├─ balance = 75000
│ ├─ calls totalBalance(Account3)
│ │ │
│ │ ├─ balance = 30000
│ │ ├─ calls totalBalance(null)
│ │ │ │
│ │ │ └─ BASE CASE: returns 0
│ │ │
│ │ └─ returns 30000 + 0 = 30000
│ │
│ └─ returns 75000 + 30000 = 105000
│
└─ returns 50000 + 105000 = 155000
Call Stack Growth: ┌─────────────────────────┐ │ Frame 4: account = null │ ← base case returns 0 ├─────────────────────────┤ │ Frame 3: balance = 30000 │ ← returns 30000 ├─────────────────────────┤ │ Frame 2: balance = 75000 │ ← returns 105000 ├─────────────────────────┤ │ Frame 1: balance = 50000 │ ← returns 155000 └─────────────────────────┘ Each call pushes a frame. Base case triggers unwinding. Frames pop and combine results upward.
Key Takeaway
Recursion is a technique where a method solves a problem by calling itself on a smaller version of the same problem. Every correct recursive method has two essential parts. The base case is the simplest input where the answer is known directly, and it stops the recursion. The recursive case does a small piece of work and then calls the method again on a reduced input. Without a proper base case the method would call itself forever and the call stack would overflow.
The way I explain it from real experience is through the sweep account feature at the National Bank of India. A customer can link savings accounts into a chain where surplus flows from one account to the next. To compute the combined balance of the whole chain I ask a simple self-similar question: the total is this account's balance plus the total of the rest of the chain. To find the total of the rest, I ask the exact same question about the next account, and so on, until I reach the end of the chain where there is nothing left to add and I return zero.
What makes this work correctly is the call stack. Each recursive call gets its own frame that remembers where to return. As I go deeper the frames pile up, and when the base case returns, the frames unwind one by one and the balances add back up from the bottom. So the deepest call returns first and the original call returns last with the final total.
The senior-level point I always add is about limits. Java does not optimize tail recursion automatically, so very deep recursion can throw a StackOverflowError. For problems that could go thousands of levels deep, I convert the recursion into an explicit loop or an explicit stack. Recursion shines when the structure is naturally self-similar, like walking linked account chains, traversing trees, or dividing sorted data, which is why I reach for it in exactly those situations and prefer iteration elsewhere.
Remember one sentence: recursion solves a problem by calling itself on a smaller input, with a base case to stop and a recursive case to shrink.
---