Unravel โบ Java concepts โบ Algorithms and data structures
Recursion
A recursive method calls itself on a smaller version of the problem until it reaches a base case it can answer directly.
At a glance
Looking up a word in a dictionary whose definition uses another word: you look that one up, which sends you to another, until you reach a word defined plainly; then each answer is carried back up the chain.
- 1Template: int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); }The if is the base case; the call with n - 1 is the smaller problem.
- 2Each call gets its own stack frame with its own variablesThe calls pile up on the way down, and the results are combined on the way back up.
- 3Typical uses: trees and graphs (visit a node, then recurse on its children), divide and conquer (merge sort, binary search), backtracking (permutations, N-Queens), and nested structures such as folders and JSON
- 4Tracing helps: write the calls for a small input (fact(3) calls fact(2) calls fact(1)) and the order in which values come back
- Without a base case, or when the argument does not shrink, the recursion never ends and the JVM throws StackOverflowError
- Naive recursion can repeat work exponentially: fib(n) = fib(n-1) + fib(n-2) recomputes the same values
- Each invocation pushes a frame with parameters, locals and a return address on the thread's stack (default size around 512 KB to 1 MB, giving roughly 10,000 to 20,000 frames for simple methods)
public class Maths { static long factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); } static int sumDigits(int n) { if (n < 10) return n; return n % 10 + sumDigits(n / 10); }}Read the full explanation (about 2 min)
A recursive method calls itself on a smaller version of the problem until it reaches a base case it can answer directly. Every recursive method needs a base case and progress toward it.
A mental model
Looking up a word in a dictionary whose definition uses another word: you look that one up, which sends you to another, until you reach a word defined plainly; then each answer is carried back up the chain.
How it works
Template: int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); }. The if is the base case; the call with n - 1 is the smaller problem.
Each call gets its own stack frame with its own variables. The calls pile up on the way down, and the results are combined on the way back up.
Typical uses: trees and graphs (visit a node, then recurse on its children), divide and conquer (merge sort, binary search), backtracking (permutations, N-Queens), and nested structures such as folders and JSON.
Tracing helps: write the calls for a small input (fact(3) calls fact(2) calls fact(1)) and the order in which values come back.
Going deeper
Without a base case, or when the argument does not shrink, the recursion never ends and the JVM throws StackOverflowError. Java does not optimise tail calls, so a recursion thousands deep (a list of 100,000 nodes) can fail even if correct; convert it to a loop with an explicit stack.
Naive recursion can repeat work exponentially: fib(n) = fib(n-1) + fib(n-2) recomputes the same values. Add a cache (memoisation) or switch to a loop to get linear time (see dynamic programming).
Recursion is often shorter and clearer than loops for recursive data; for plain counting loops it is only slower.
Under the hood
Each invocation pushes a frame with parameters, locals and a return address on the thread's stack (default size around 512 KB to 1 MB, giving roughly 10,000 to 20,000 frames for simple methods). Returning pops the frame.
Common mistakes
- Missing or wrong base case.
- The argument not getting smaller.
- Exponential recomputation.
- Recursing over very deep structures.
How Unravel recognises it
When you paste code, Unravel looks for these signs of recursion. Spotting them yourself is a good habit when you read unfamiliar code:
- Language constructs:
recursion
Part of a learning path
- Algorithms and data structures ยท previous: Time complexity (Big O) ยท next: Binary search
Related concepts
Frequently asked questions
What is Recursion?
A recursive method calls itself on a smaller version of the problem until it reaches a base case it can answer directly. Every recursive method needs a base case and progress toward it.
What are the most common mistakes with Recursion?
Missing or wrong base case. The argument not getting smaller. Exponential recomputation. Recursing over very deep structures.
How can I see Recursion in real code?
Paste your own Java into Unravel and it will point out where recursion appears, explain how it works at the detail level you choose, and draw the flow of the code around it.