Understanding Recursion in Java
Recursion is a programming technique where a method calls itself to solve smaller instances of the same
problem. A classic real-world analogy is nested dolls: each doll contains a smaller one inside, and you keep
opening them until you reach the smallest doll. In recursion, each call “opens” the problem into a simpler
version until a base case (the smallest doll) is reached 1 . Java implements recursion using the call stack, a
LIFO (Last-In, First-Out) structure in memory. Each time a recursive method is invoked, a new frame (with its
arguments and local variables) is pushed onto the stack; when a method returns, its frame is popped off
2 . This push-pop behavior is analogous to stacking books: you can only add or remove the top book.
Recursion leverages the call stack in memory. When a function is called, its execution context (code,
parameters, local variables) is pushed on top of the stack; when it finishes, it is popped off 2 . This means
nested recursive calls accumulate stack frames. A stack overflow (exceeding the stack size) occurs if
recursion goes too deep without returning. For example, calling a function without a proper base case will
keep pushing new frames until memory is exhausted 3 . In contrast, a loop uses a single function call,
adding nothing new to the call stack beyond that one frame 4 .
How Recursion Works in Java
When a Java method calls itself, the JVM allocates a new stack frame for that call. Each frame holds the
method’s parameters, local variables, and the return address. When the recursive method makes a further
self-call, another frame is pushed on top, and so on. Eventually, a base case stops further recursion and the
call returns. The JVM then unwinds the stack: each returning call pops its frame, passing its result to the
caller below. In the factoral example below, each call prints before recursing (as it’s pushed), and prints after
returning (as it pops) to illustrate this order.
1
Consider factorial as an example. An iterative (loop) version uses one activation of the function, so only one
frame is pushed; when it computes the result, it returns immediately (left side). A recursive version calls
itself (factorial(n) calls factorial(n–1)), so multiple frames accumulate on the stack (right side). Each frame
waits for the next to return before it can complete and pop off 4 . Thus recursion trades off extra stack
usage for cleaner code. Each recursive call has its own copy of parameters and locals, completely
independent of other calls 2 5 .
Base Case vs Recursive Case
A recursive function has two main parts: the base case and the recursive case. The base case is a simple
condition that can be answered directly without further recursion. It prevents infinite recursion by providing
a stopping point. The recursive case reduces the original problem toward the base case by calling the same
function with a smaller or simpler input. For example, in computing factorial, the base case is when n ≤ 1
(we know 1! = 1), and the recursive case multiplies n by factorial(n–1).
A well-placed base case is crucial. If you omit or misplace it, the method will keep calling itself forever (or
until the stack overflows) 6 3 . In Java, common base cases include checking if a number is 0 or 1, or if an
index has reached the end of an array. When the base case condition is met, the function returns
immediately, and recursion unwinds. For example, in a string palindrome check using two indices, the base
case is when the left index ≥ right index (all characters have been matched) 7 . In sum, the base case
answers the smallest subproblem directly, and the recursive case breaks the problem into smaller parts
until the base case is reached 6 .
Example: Factorial (n!)
The factorial of a non-negative integer n (written n!) is the product of all positive integers up to n (for
example, 5! = 5×4×3×2×1). Recursively, n! = n * (n-1)!, with base case 0! = 1 or 1! = 1. Here is a Java
implementation with dry-run comments:
2
public static int factorial(int n) {
// Base case: 0! = 1 and 1! = 1
if (n <= 1) {
// When n is 0 or 1, stop recursion
return 1;
}
// Recursive case: n! = n * (n-1)!
int result = n * factorial(n - 1);
return result;
}
Dry-run: To compute factorial(4) , the calls unfold as: factorial(4) calls factorial(3) , which
calls factorial(2) , which calls factorial(1) . At n=1 , the base case returns 1. Then the calls
resolve in reverse order: factorial(2) returns 2*1=2 , factorial(3) returns 3*2=6 , and
factorial(4) returns 4*6=24 . Each call waits for the deeper call to return before finishing. As a result,
the final output is 24 (for n=4). This process is exactly illustrated in many recursion tutorials: each “start of
factorial n=…” print happens as the calls are pushed on the stack, and each “end of factorial, result=…” print
happens as calls return 8 .
Example: Fibonacci Sequence
The Fibonacci sequence is defined by F(0)=0, F(1)=1, and F(n) = F(n-1) + F(n-2) for n≥2. A naive recursive
solution is straightforward but inefficient (exponential time), as it recomputes many values. Here is a simple
Java version:
public static int fib(int n) {
// Base cases: fib(0)=0, fib(1)=1
if (n == 0 || n == 1) {
return n;
}
// Recursive case: sum of two previous Fibonacci numbers
return fib(n - 1) + fib(n - 2);
}
Walkthrough: For fib(5) , this will compute fib(4)+fib(3) ; fib(4) computes fib(3)+fib(2) ,
and so on. The recursion tree grows exponentially, as each call usually splits into two more calls. For
example, fib(5) calls fib(4) and fib(3) . fib(4) calls fib(3) and fib(2) . Notice that
fib(3) is computed twice (once as part of fib(4) and once directly). This redundancy is costly. To optimize,
we can use memoization: store results in an array or map after computing them once, so future calls reuse
the result. Alternatively, one can convert the recursion into a loop with dynamic programming in O(n) time.
Regardless, the base cases (n=0 or 1) stop recursion, and each recursive call brings n closer to these base
cases.
3
Example: Sum of an Array
We can recursively compute the sum of all elements in an array. The idea is: the sum of the first n elements
equals the sum of the first (n–1) elements plus the nth element.
public static int sumArray(int[] arr, int n) {
// Base case: no elements to sum
if (n <= 0) {
return 0;
}
// Sum of first n-1 elements plus last element
return sumArray(arr, n - 1) + arr[n - 1];
}
// Helper to call easily:
public static int sumArray(int[] arr) {
return sumArray(arr, [Link]);
}
In this code, sumArray(arr, n) returns the sum of the first n elements (indexes 0 to n–1). The base
case n <= 0 returns 0 (empty sum). Otherwise, we add arr[n-1] to the sum of the previous elements.
Each recursive call reduces n by 1, so we eventually reach 0. The approach is to “take the last element and
recurse on the rest.” GeeksforGeeks describes this clearly: “Each step reduces the array size, summing the last
element with the sum of the remaining elements until the base case is reached.” 9 . For example,
sumArray([1,2,3,4], 4) = sumArray([1,2,3,4],3) + 4 ; next + 3 , + 2 , + 1 , then base
returns 0.
Example: Binary Search (Recursive)
Binary search can be implemented recursively on a sorted array by dividing the search interval in half each
time. Here’s a Java example:
public static int binarySearch(int[] arr, int left, int right, int x) {
if (left > right) {
// Base case: not found
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == x) {
return mid; // Found x at mid
}
if (arr[mid] > x) {
// x lies in left half
return binarySearch(arr, left, mid - 1, x);
} else {
// x lies in right half
4
return binarySearch(arr, mid + 1, right, x);
}
}
To use it, call binarySearch(arr, 0, [Link]-1, target) . At each call, we compare the target
x with arr[mid] . If equal, we found it; otherwise we recurse either left or right by adjusting left and
right . The base case is when left > right (the subarray is empty), we return -1 indicating “not
found.” This recursion will at most descend $\log N$ levels (for array length N), so it’s efficient. In each
recursion, we cut the search range roughly in half. This example follows the same base/recursive
structure: check if the segment is invalid (base), otherwise pick a mid and recurse.
Example: Palindrome Check
String palindrome: We can check if a string is a palindrome (reads the same forward and backward) by
comparing its first and last characters, then recursively checking the substring between them. Here’s one
approach using two indices:
public static boolean isPalindrome(String s, int left, int right) {
// Base case: checked all pairs
if (left >= right) {
return true;
}
// If mismatch, not a palindrome
if ([Link](left) != [Link](right)) {
return false;
}
// Recurse on the remaining substring
return isPalindrome(s, left + 1, right - 1);
}
// Driver
public static boolean isPalindrome(String s) {
return isPalindrome(s, 0, [Link]() - 1);
}
This follows the typical two-pointer recursive approach: if the characters at left and right match, we
move inward. The base case (left ≥ right) means we’ve checked all pairs and found no mismatch, so it is a
palindrome 7 . If any pair mismatches, we immediately return false.
Number palindrome: We can also check if an integer is a palindrome by reversing its digits recursively. One
way is to write a helper that builds the reverse:
public static int reverseNumber(int n, int rev) {
if (n == 0) {
return rev; // All digits processed
5
}
return reverseNumber(n / 10, rev * 10 + (n % 10));
}
// Then check:
public static boolean isPalindromeNumber(int n) {
if (n < 0) return false; // negative numbers not palindrome by this
definition
int rev = reverseNumber(n, 0);
return (rev == n);
}
The reverseNumber function takes off the last digit n%10 each time, appends it to rev , and calls itself
with n/10 , until n is 0 (base case). If the reversed number equals the original, it is a palindrome. For
example, 121 -> revBuild 121 -> equal, so return true.
Example: Power Calculation (x^n)
We can compute x^n (x raised to the power n) using recursion. A straightforward recursive method
multiplies the base by itself:
public static double power(double base, int exponent) {
// Base case: exponent zero
if (exponent == 0) {
return 1;
}
// If exponent is negative, handle by reciprocal
if (exponent < 0) {
return 1 / power(base, -exponent);
}
// Recursive case: multiply by base one fewer times
return base * power(base, exponent - 1);
}
This function returns 1 when exponent is 0 (since any number^0 = 1), and for positive exponents it does
base * power(base, exponent - 1) . For negative exponents it uses the fact that $x^{-n} = 1/(x^n)$.
Each recursive call reduces exponent by 1, so it eventually reaches 0 10 . For example, power(2, 3)
computes 2 * power(2,2) = 2 * (2 * power(2,1)) = 2 * (2 * (2 * power(2,0))) =
2*2*2*1 = 8 .
Optimized exponentiation: The above is $O(n)$. We can optimize using exponentiation by squaring in
$O(\log n)$ time. The idea is:
public static double fastPower(double base, int exponent) {
if (exponent == 0) return 1;
6
if (exponent < 0) return 1 / fastPower(base, -exponent);
// Divide: compute power(base, exponent/2)
double half = fastPower(base, exponent / 2);
// If exponent is even, square the half result.
if (exponent % 2 == 0) {
return half * half;
} else {
// If odd, multiply by base one more time
return base * half * half;
}
}
This halves the exponent each time, leading to a much faster solution for large exponents.
Example: Generating All Subsets (Power Set)
The power set of a set is the set of all its subsets. Recursively, for each element, you can choose to include it
or exclude it in each subset. For example, subsets of “abc” are found by: for each subset of “bc”, make one
version without ‘a’ and one with ‘a’ prepended 11 . Here’s a Java example using strings:
public static void powerSet(String str, int index, String curr) {
int n = [Link]();
// Base case: reached end of string
if (index == n) {
[Link](curr);
return;
}
// Include [Link](index)
powerSet(str, index + 1, curr + [Link](index));
// Exclude [Link](index)
powerSet(str, index + 1, curr);
}
// Driver:
powerSet("abc", 0, ""); // prints all subsets of "abc"
In this code, powerSet(str, index, curr) explores two recursive cases at each index: one that
includes the current character (appending it to curr ), and one that excludes it 11 . When index
reaches the string length (base case), we have built a complete subset in curr and print it. This produces
subsets in any order, e.g. { "", "c", "b", "bc", "a", "ac", "ab", "abc" } for “abc”. The total
number of recursive calls is $2^n$ for n characters (every subset).
Example: Generating Permutations
To generate all permutations of a string (or array), a common recursive approach is to pick each character in
turn as the first character, then permute the remaining characters. Here’s an example:
7
public static void permute(String str, String prefix) {
// Base case: no characters left to permute
if ([Link]()) {
[Link](prefix);
return;
}
// Recursive case: for each character in str, fix it and permute the rest
for (int i = 0; i < [Link](); i++) {
char ch = [Link](i);
// Form the remaining string without the i-th char
String rem = [Link](0, i) + [Link](i + 1);
// Recurse with prefix + ch and the remainder
permute(rem, prefix + ch);
}
}
// Driver:
permute("abc", ""); // prints all permutations of "abc"
This matches the classic solution described in GeeksforGeeks: when str is empty, we have one
permutation in prefix ; otherwise we loop over each character ch in str , remove it, and recurse on
the remainder 12 13 . For “abc”, this will print abc, acb, bac, bca, cab, cba . If characters may
repeat and you want distinct permutations, you would add a boolean array check to avoid duplicating work
as shown in advanced versions 14 . The time complexity is $O(N \times N!)$ for a string of length N (there
are N! permutations and each takes O(N) to form).
Example: Tower of Hanoi
The Tower of Hanoi puzzle has 3 pegs and n disks of different sizes on the first peg, largest on bottom. The
goal is to move all disks to the third peg, obeying these rules: (1) move one disk at a time, (2) never place a
larger disk on top of a smaller one. The classic recursive solution is: move n-1 disks to the auxiliary peg,
move the largest disk to target, then move the n-1 disks from auxiliary to target 15 .
In Java:
public static void towerOfHanoi(int n, char fromPeg, char toPeg, char auxPeg) {
// Base case: move one disk directly
if (n == 1) {
[Link]("Move disk 1 from " + fromPeg + " to " + toPeg);
return;
}
// Move n-1 disks from source to auxiliary, using target as a buffer
towerOfHanoi(n-1, fromPeg, auxPeg, toPeg);
// Move the largest disk to target
[Link]("Move disk " + n + " from " + fromPeg + " to " + toPeg);
// Move the n-1 disks from auxiliary to target, using source as a buffer
8
towerOfHanoi(n-1, auxPeg, toPeg, fromPeg);
}
The base case occurs when n == 1 : we just move that single disk and return 16 . For n > 1 , we
recursively break the problem into moving n-1 disks twice. For example, with 3 disks (1 smallest, 3
largest), the steps are: move disk 1 and 2 to the auxiliary peg, move disk 3 to target, then move disks 1 and
2 from auxiliary to target. This recursion naturally creates a call tree and correctly solves the problem in
$2^n - 1$ moves. The algorithm’s correctness comes from correctly choosing base case and recursion steps.
Example: Recursively Reversing a Linked List
Reversing a singly linked list recursively means rearranging its pointers so the last node becomes the head.
Here’s a common pattern, assuming a simple ListNode { int val; ListNode next; } :
public static ListNode reverseList(ListNode head) {
// Base case: empty list or single node
if (head == null || [Link] == null) {
return head; // New head of reversed list
}
// Recurse on rest of the list
ListNode newHead = reverseList([Link]);
// [Link] is now the last node of reversed rest; link it back to head
[Link] = head;
[Link] = null;
return newHead; // Propagate new head upward
}
This follows the idea in Java StackOverflow discussions: the recursion reverseList([Link])
reverses all but the first node. Then we set [Link] = head to link the old second node back to
the first, and [Link] = null to terminate the list. The base case is when the list is empty or has one
node. The returned newHead is passed up through all calls so the original caller gets the new head of the
reversed list 17 . For example, if the list is 1→2→3, the recursive calls go reverseList(1) ->
reverseList(2) -> reverseList(3) , at which point reverseList(3) returns the node 3 (as new
head). Then unwinding, we link 3→2 and set 2→null, then link 2→1 and set 1→null. The end result is
3→2→1.
Recursion in Backtracking (Overview)
Many backtracking problems rely on recursion to systematically explore choices and backtrack on failure.
Backtracking incrementally builds a solution by making a choice, recursing to explore further choices, and
undoing that choice if it leads to no solution 18 . Classic examples include Sudoku solving, N-Queens,
generating all subsets or permutations (which we covered), and solving mazes. The backtracking recursion
tree explores all valid paths and backtracks (undoes) when a constraint is violated. For instance, generating
valid parentheses combinations or searching all paths in a maze uses recursion to try one option, recurse,
and then revert if needed. In Java, each recursive call holds the partial solution in the call stack; if a dead
9
end is reached, the function returns (popping that frame) and the previous call tries a different option 18 .
While backtracking is conceptually straightforward, it often has exponential time complexity since it
explores many combinations.
Pro Tips: Avoiding Stack Overflow and Optimizing Recursion
• Watch the base case: Always ensure your base case is correct and reachable. A wrong base case is
the most common cause of stack overflow (infinite recursion) 3 . If recursion is unexpectedly deep,
check your termination condition.
• Tail recursion (not optimized in Java): Tail-recursive methods (where the recursive call is the last
action) can sometimes be converted to iteration manually to avoid stack growth. Java does not
guarantee tail-call optimization, so deep tail recursion will still overflow. If you notice you’re just tail-
recursing, consider rewriting it as a loop.
• Memoization / Dynamic Programming: For recursive algorithms with overlapping subproblems (like
Fibonacci), use memoization to cache results. Store computed results in an array or map so repeated
calls return immediately. This turns exponential recursion into polynomial time. For example, a
memoized Fibonacci or factorial using a static map will run in linear time.
• Convert to iteration when possible: Some recursive algorithms have iterative equivalents. For
instance, depth-first search on a graph can use an explicit stack instead of recursion. If stack depth is
a concern, refactoring recursion into a loop may help.
• Increase stack size (advanced): Rarely, you might adjust JVM stack size if legitimate recursion depth
is very high (e.g., large tree depth). But this is usually not needed if algorithms are well-designed.
Recursion is powerful but should be used judiciously with these tips to avoid common pitfalls. In practice,
analyze if recursion is the clearest solution or if an iterative or DP approach makes more sense for
performance.
Practice Problems
Test your understanding with these problems. Each includes a description and a recursive solution in Java.
1. Sum of Digits: Write a recursive function sumDigits(int n) that returns the sum of the digits of
n .
Solution: The base case is when n == 0 (sum is 0). Otherwise, return (n % 10) +
sumDigits(n / 10) .
public static int sumDigits(int n) {
if (n == 0) return 0;
return (n % 10) + sumDigits(n / 10);
}
// Example: sumDigits(425) returns 4+2+5 = 11.
2. Count Occurrences in Array: Given an array arr and a target x , write
countOccurrences(arr, n, x) that returns how many times x appears in the first n
elements of arr .
10
Solution: Base case: n == 0 returns 0. Otherwise, check arr[n-1] : if it equals x , add 1; then
recurse on n-1 .
public static int countOccurrences(int[] arr, int n, int x) {
if (n == 0) return 0;
int count = (arr[n-1] == x) ? 1 : 0;
return count + countOccurrences(arr, n - 1, x);
}
// Example: countOccurrences([1,2,1,3], 4, 1) returns 2.
3. Check if Array is Sorted: Write isSorted(arr, n) that returns true if the first n elements of
arr are in ascending order.
Solution: Base case: if n <= 1 , it’s sorted (true). Otherwise, check if arr[n-2] <= arr[n-1] ; if
not, return false. If yes, recurse on n-1 .
public static boolean isSorted(int[] arr, int n) {
if (n <= 1) return true;
if (arr[n-2] > arr[n-1]) return false;
return isSorted(arr, n - 1);
}
// Example: isSorted([1,3,5,5,7], 5) returns true; isSorted([1,4,3], 3)
returns false.
4. Generate Valid Parentheses: Given n pairs of parentheses, write a function to print all
combinations of well-formed parentheses. (This is a classic backtracking problem.)
Solution Outline: Use recursion with two counters: open and close . At each step, if open <
n , you can add '(' ; if close < open , you can add ')' . Stop when the string length is 2*n .
public static void generateParens(String curr, int open, int close, int n)
{
if ([Link]() == 2 * n) {
[Link](curr);
return;
}
if (open < n) {
generateParens(curr + "(", open + 1, close, n);
}
if (close < open) {
generateParens(curr + ")", open, close + 1, n);
}
}
// Driver:
11
generateParens("", 0, 0, 3);
// Example output for n=3: ((())), (()()), (())(), ()(()), ()()().
5. Compute Binomial Coefficient (nCr): Write nCr(n, r) that computes “n choose r” using
recursion. Recall nCr = (n-1)C(r-1) + (n-1)C(r), with base cases nC0 = 1 and nCn = 1.
public static int nCr(int n, int r) {
// Base cases
if (r == 0 || r == n) return 1;
// Recursive formula
return nCr(n - 1, r - 1) + nCr(n - 1, r);
}
// Example: nCr(5, 2) returns 10.
Each of the above solutions uses a clear base case and a recursive step that reduces the problem size. Try
walking through each code with sample inputs (dry runs) to see the call stack behavior. These exercises
reinforce understanding of recursion patterns.
Moving Forward: Recursion in Trees
Understanding recursion thoroughly equips you to tackle recursion on tree data structures next. Tree
problems (like traversals, tree height, path sums, etc.) naturally use recursion, since each node branches to
children. Once you are comfortable with the principles above – base cases, call stack, backtracking – you’ll
find tree recursion straightforward. In short, recursion on trees often follows the same patterns: handle the
current node (base case for null), then recurse on left/right children. Mastering the above examples ensures
you have the foundation to handle trees and more complex recursive structures confidently.
Sources: This guide was informed by standard recursion tutorials and examples 2 6 5 9 7 11 19
18 , adapted into a cohesive Java-focused explanation.
1 Understanding Recursion Through Real-World Examples
[Link]
2 4 Recursion Call-Stack | CS1335 Java and Processing
[Link]
3 5 Recursion in Java - GeeksforGeeks
[Link]
6 What is 'Base Case' in Recursion? - GeeksforGeeks
[Link]
7 Recursive function to check if a string is palindrome - GeeksforGeeks
[Link]
12
8 Recursion and the Call Stack: An Explanation of Recursive Functions for Beginners | by Marc Rodriguez |
Medium
[Link]
9 Sum of array elements using recursion - GeeksforGeeks
[Link]
10 Java Program to calculate the power using recursion | Vultr Docs
[Link]
11 Recursive program to generate power set - GeeksforGeeks
[Link]
12 13 14 19 Print all permutations of a string in Java - GeeksforGeeks
[Link]
15 16 Tower of Hanoi - Algorithm and Implementation in Java | DigitalOcean
[Link]
17 data structures - Reversing a linked list in Java, recursively - Stack Overflow
[Link]
18 Introduction to Backtracking - GeeksforGeeks
[Link]
13