Practice Now
Java
Recursive Algorithms
Optimization
Programming Techniques
Software Development

Optimisation of recursive algorithm in Java

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
AlgorithmsComplexity & PerformanceJava

Introduction

Recursive algorithms in Java are elegant but can be extremely inefficient due to redundant computations and deep call stacks. The three main optimization techniques are memoization (caching results of subproblems), converting to iterative solutions (eliminating stack overhead), and tail-call optimization (though the JVM does not optimize tail calls automatically). Understanding when and how to apply these transforms is critical for production Java code.

The Problem: Exponential Fibonacci

java
1// Naive recursive Fibonacci: O(2^n) time, O(n) stack
2public static long fib(int n) {
3    if (n <= 1) return n;
4    return fib(n - 1) + fib(n - 2);
5}
6
7fib(45); // Takes about 6 seconds
8fib(50); // Takes about 60 seconds, unusable

fib(5) calls fib(3) twice, fib(2) three times, and fib(1) five times. The same subproblems are solved repeatedly.

Fix 1: Memoization (Top-Down DP)

Cache results in a HashMap or array to avoid recomputation:

java
1import java.util.HashMap;
2import java.util.Map;
3
4public class Fibonacci {
5    private static Map<Integer, Long> memo = new HashMap<>();
6
7    public static long fib(int n) {
8        if (n <= 1) return n;
9        if (memo.containsKey(n)) return memo.get(n);
10
11        long result = fib(n - 1) + fib(n - 2);
12        memo.put(n, result);
13        return result;
14    }
15}
16
17// fib(50) now returns instantly. O(n) time, O(n) space

With an array instead of HashMap for better performance:

java
1public static long fib(int n) {
2    long[] memo = new long[n + 1];
3    Arrays.fill(memo, -1);
4    return fibHelper(n, memo);
5}
6
7private static long fibHelper(int n, long[] memo) {
8    if (n <= 1) return n;
9    if (memo[n] != -1) return memo[n];
10    memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
11    return memo[n];
12}

Fix 2: Iterative Solution (Bottom-Up DP)

Eliminate the call stack entirely by computing bottom-up:

java
1public static long fib(int n) {
2    if (n <= 1) return n;
3    long prev2 = 0, prev1 = 1;
4    for (int i = 2; i <= n; i++) {
5        long current = prev1 + prev2;
6        prev2 = prev1;
7        prev1 = current;
8    }
9    return prev1;
10}
11
12// O(n) time, O(1) space. Optimal

No stack overflow risk, no HashMap overhead, minimal memory.

Fix 3: Tail Recursion Conversion

Convert to tail-recursive form (accumulator pattern):

java
1// Not tail-recursive: result depends on recursive call
2public static long factorial(int n) {
3    if (n <= 1) return 1;
4    return n * factorial(n - 1);  // Multiplication AFTER the call
5}
6
7// Tail-recursive: result is computed before the call
8public static long factorial(int n) {
9    return factorialHelper(n, 1);
10}
11
12private static long factorialHelper(int n, long accumulator) {
13    if (n <= 1) return accumulator;
14    return factorialHelper(n - 1, n * accumulator);  // Last operation is the call
15}

Note: The JVM does not optimize tail calls. The tail-recursive version still uses O(n) stack in Java. Convert to a loop for real optimization:

java
1public static long factorial(int n) {
2    long result = 1;
3    for (int i = 2; i <= n; i++) {
4        result *= i;
5    }
6    return result;
7}

Fix 4: Stack-Based Iteration (for Tree Recursion)

Replace recursive tree traversal with an explicit stack:

java
1// Recursive DFS: risk of StackOverflowError on deep trees
2public static void dfs(TreeNode node) {
3    if (node == null) return;
4    process(node);
5    dfs(node.left);
6    dfs(node.right);
7}
8
9// Iterative DFS: no stack overflow risk
10public static void dfs(TreeNode root) {
11    Deque<TreeNode> stack = new ArrayDeque<>();
12    if (root != null) stack.push(root);
13
14    while (!stack.isEmpty()) {
15        TreeNode node = stack.pop();
16        process(node);
17        if (node.right != null) stack.push(node.right);
18        if (node.left != null) stack.push(node.left);
19    }
20}

Fix 5: Divide and Conquer Optimization

Merge sort is recursive but already efficient. However, for small subarrays, switch to insertion sort:

java
1public static void mergeSort(int[] arr, int lo, int hi) {
2    if (hi - lo <= 15) {
3        // Insertion sort for small subarrays, less overhead
4        insertionSort(arr, lo, hi);
5        return;
6    }
7    int mid = lo + (hi - lo) / 2;
8    mergeSort(arr, lo, mid);
9    mergeSort(arr, mid + 1, hi);
10    merge(arr, lo, mid, hi);
11}

Java's Arrays.sort() uses this hybrid approach (TimSort).

Java-Specific Considerations

Stack Size

java
1// Default thread stack size is roughly 512KB-1MB
2// Deep recursion causes StackOverflowError
3
4// Increase stack size for a specific thread
5Thread thread = new Thread(null, () -> {
6    long result = deepRecursion(1_000_000);
7    System.out.println(result);
8}, "deep-stack", 64 * 1024 * 1024); // 64MB stack
9thread.start();
10
11// Or JVM flag: -Xss4m

ConcurrentHashMap for Thread-Safe Memoization

java
1import java.util.concurrent.ConcurrentHashMap;
2
3private static final ConcurrentHashMap<Integer, Long> memo =
4    new ConcurrentHashMap<>();
5
6public static long fib(int n) {
7    if (n <= 1) return n;
8    return memo.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2));
9}

Warning: computeIfAbsent with recursive calls can deadlock on ConcurrentHashMap due to bucket locking. Use a regular HashMap for single-threaded memoization.

Real-World Example: Path Counting

java
1// Count paths in a grid from top-left to bottom-right
2// Naive: O(2^(m+n))
3public static int countPaths(int m, int n) {
4    if (m == 1 || n == 1) return 1;
5    return countPaths(m - 1, n) + countPaths(m, n - 1);
6}
7
8// Memoized: O(m*n)
9public static int countPaths(int m, int n, int[][] memo) {
10    if (m == 1 || n == 1) return 1;
11    if (memo[m][n] != 0) return memo[m][n];
12    memo[m][n] = countPaths(m - 1, n, memo) + countPaths(m, n - 1, memo);
13    return memo[m][n];
14}
15
16// Iterative DP: O(m*n) time, O(n) space
17public static int countPaths(int m, int n) {
18    int[] dp = new int[n];
19    Arrays.fill(dp, 1);
20    for (int i = 1; i < m; i++) {
21        for (int j = 1; j < n; j++) {
22            dp[j] += dp[j - 1];
23        }
24    }
25    return dp[n - 1];
26}

Common Pitfalls

  • StackOverflowError: Java's default stack is small. Recursive depth over roughly 5,000-10,000 frames crashes. Convert deep recursion to iteration or increase thread stack size.
  • HashMap overhead for memoization: For integer keys, use an array (long[n+1]) instead of HashMap<Integer, Long>. Arrays are faster and use less memory due to no boxing.
  • ConcurrentHashMap.computeIfAbsent deadlock: Recursive calls inside computeIfAbsent can deadlock when two keys hash to the same bucket. Use a plain HashMap or pre-populate the cache.
  • Assuming JVM optimizes tail calls: Unlike Scala or Kotlin (with tailrec), Java does not optimize tail recursion. Always convert tail-recursive methods to loops manually.
  • Forgetting base cases: Missing or incorrect base cases cause infinite recursion. Always verify that every recursive path eventually reaches a base case.

Summary

  • Memoization transforms exponential recursion to polynomial time by caching subproblem results
  • Bottom-up iteration (tabulation) eliminates call stack overhead entirely
  • Use arrays instead of HashMap for integer-keyed memoization
  • Replace recursive tree/graph traversals with explicit stack for deep structures
  • Java does not optimize tail calls. Convert tail recursion to loops manually
  • For hybrid approaches, switch to simple algorithms (insertion sort) for small inputs
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.