Some Random Notes

3. Recursion Tradeoff

3 min read

Pros

It’s very readable, compact, and showcases a solid understanding of recursion.

Cons

  • Performance - Because it uses recursion, it adds overhead to the call stack. For a string of length , it uses stack space in the worst case, plus the memory already allocated by replaceAll() and toLowerCase(). - Latency - Recursion increases latency and memory usage in Java. - Recursive solution of Palindrome example in java took 17 ms while iterative one ran in a lightning-fast 1 ms.

Factors of Latency

  • Stack Frame Overhead:
    • Every time a recursive function calls itself, Java must create a new “stack frame” in memory to keep track of local variables, parameters, and where to return when the function finishes. Doing this thousands of times adds massive overhead.
  • CPU Cycle Cost:
    • Jumping back and forth between stack frames requires extra CPU operations compared to staying inside a single loop.
  • The StackOverflowError Risk:
    • If a strings is up to characters long. A recursion depth that deep will actually crash with a StackOverflowError on large test cases in Java because the JVM runs out of stack memory.

Iterative two-pointer solution avoids all of that overhead by reusing the exact same stack frame and utilizing simple CPU register operations. That’s why iteration wins big here!

Metaspace vs Stack

Metaspace = Host OS memory

So stackoverlfow and outofheap memory should hardly comes into picture ?

That is a common point of confusion, but Metaspace and the JVM Stack are entirely different memory regions!

Here is how JVM memory is actually partitioned and why StackOverflowError still happens regardless of how much OS memory you have:

The Core JVM Memory Regions

  • Metaspace:
    • This is where the JVM stores class definitions, method metadata, and static variables.
    • Since Java 8, it dynamically grows using host OS memory, meaning you rarely hit "out of metaspace" unless you have a massive class-loading leak.
  • The JVM Stack (Thread Stack):
    • Every individual thread in Java gets its own private stack (controlled by the -Xss flag, typically around 1 MB per thread).
    • This stack stores local primitive variables, method arguments, and stack frames for active method calls.
  • The Heap: Where dynamic objects (String, arrays, ArrayList, etc.) live.

Why StackOverflowError Happens

When a recursive function calls itself, a new stack frame is pushed onto that specific thread’s JVM Stack. Because each thread’s stack size is fixed (usually 1 MB), if your recursion goes too deep (e.g., 10,000 recursive calls deep for a long string), it will exhaust that 1 MB limit and throw a StackOverflowError immediately—even if your host OS has 64 GB of free RAM. The OS memory cannot dynamically expand a single thread’s assigned stack region past its configured limit.

What about OutOfMemoryError (Heap)?

If you instead created a massive data structure or kept allocating new strings inside that recursion, you would eventually hit a java.lang.OutOfMemoryError: Java heap space. But deep recursion specifically kills you on stack depth, not heap size or metaspace.

Backlinks