Recursion

Recursion

1. What Is Recursion? (beginner)

Recursion = method calls itself to solve smaller piece. Needs base case (stop!) + recursive case (shrink!). Like Russian dolls: open until smallest!

2. Classic — Factorial (trace this!)

static int fact(int n) {
    if (n <= 1) return 1;      // BASE (stop! no call!)
    return n * fact(n - 1);    // RECURSE (smaller!)
}
// fact(4) = 4*fact(3) = 4*3*fact(2) = 4*3*2*1 = 24
// stack: fact4 → fact3 → fact2 → fact1(return!) → unwind ×!

Fibonacci + sum variants:

static int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }
static int sum(int n) { if (n == 0) return 0; return n + sum(n-1); }

3. Rules (exam traps!)

• NO base → StackOverflowError (infinite frames!).
• Must shrink toward base (fact(n) calling fact(n) = infinite!).
• Each call has OWN params/locals (frames!). Return unwinds.

4. Recursion vs Loop

Recursion = elegant (trees, factorial) but slower + stack risk. Loop = fast, no overflow. Exams ask both versions!

5. Exam Points

• Factorial + trace/stack — 7 marks, very frequent.
• Base-need + overflow cause — 3 marks, frequent.