Methods

Recursion

Complete lesson for Recursion using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with Java OOP and Collections where relevant.

Basics — Recursion

Section: Methods. Base case, recursive case, the call stack, and why the JVM does not tail-call optimize.

What is recursion?

A method that calls itself (directly or indirectly) until a **base case** stops the chain.
Every call gets its own stack frame: parameters, locals, and return address. Too many frames → StackOverflowError.
Think “smaller problem + combine”, not “loop in disguise”, when you first learn it.

public class FactorialRec {
    static long fact(int n) {
        if (n < 0) throw new IllegalArgumentException("n >= 0");
        if (n <= 1) return 1;          // base case
        return n * fact(n - 1);        // recursive case
    }

    public static void main(String[] args) {
        System.out.println(fact(5));   // 120
    }
}

Design rules

Always write the base case first. Then make a call that moves toward that case (n - 1, mid, head.getNext()).
Multiple base cases are normal (empty tree, n == 0 and n == 1 for Fibonacci).
Helper methods (rec(arr, lo, hi)) keep the public API clean.

Classic examples

Problem	Base case	Recursive idea
Factorial	`n <= 1`	`n * fact(n-1)`
Fibonacci	`n <= 1`	`fib(n-1)+fib(n-2)` (slow)
Binary search	`lo > hi`	Halve the range
Linked-list length	`node == null`	`1 + length(next)`
Directory walk	file, not dir	Recurse into children

Advanced — Recursion

Stack, memoization, and tail calls

Naive fib(n) is O(φⁿ) time. Memoize with an array/HashMap or use an iterative loop — interviews expect you to mention this.
The JVM (HotSpot) does **not** perform tail-call optimization. A “tail recursive” method still consumes a stack frame per call.
Default stack size is small (often ~1 MB). Deep trees or fact(100000) will blow the stack — use iteration or an explicit ArrayDeque as a stack.
Mutual recursion (isEven → isOdd → isEven) is legal but harder to debug.

Tricky Interview Points

Q1) What is a base case?

Answer The condition that returns without another recursive call. Without it you get infinite recursion and StackOverflowError.

Q2) Recursion vs iteration?

Answer Anything recursive can be iterative with an explicit stack. Recursion is clearer for trees; iteration is safer for deep linear cases in Java.

Q3) Does Java optimize tail recursion?

Answer No. HotSpot does not guarantee TCO. Prefer loops for large n.

Q4) Why is naive Fibonacci slow?

Answer It recomputes the same subproblems exponentially. Time is exponential; a memoized or iterative version is O(n).

Q5) What exception does infinite recursion throw?

Answer StackOverflowError (an Error, not a checked Exception). Catching it is almost never the right fix.

Q6) How do you recurse over a binary tree?

Answer Visit node, then recurse left and right. Base case is null child. DFS is naturally recursive; BFS uses a Queue.

Simple Programs

Fibonacci: naive vs memoized

import java.util.HashMap;
import java.util.Map;

public class FibDemo {
    static long fibNaive(int n) {
        if (n <= 1) return n;
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    static long fibMemo(int n, Map<Integer, Long> memo) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        long v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        memo.put(n, v);
        return v;
    }

    public static void main(String[] args) {
        System.out.println(fibNaive(10));
        System.out.println(fibMemo(40, new HashMap<>()));
    }
}

Problem Solving Tricks

Print the call stack with a depth parameter while learning (indent + n).
Convert “process list head, recurse on tail” to a loop once it works.
For interview trees, always ask: can the root be null?
Use long for factorial/Fibonacci — int overflows quietly at 13! / fib(47).

Practice Programs List

Write recursive sum(int[] a, int i) that sums from index i.
Implement binary search recursively on a sorted array.
Reverse a string with recursion (s.charAt + substring, then rewrite with indexes).
Compute GCD with Euclid’s algorithm recursively.
Draw the call tree for fib(5) on paper, then memoize it.