JAVA — CHAPTER 22

Recursion and Big O · Concept Cheat Sheet

Recursion Basics Factorial / Fibonacci Towers of Hanoi Fractals Big O Notation

1 RECURSION — THE CORE IDEA

Every recursive method needs

A base case — the simplest input, solved directly, no further recursion
A recursive case — solves a smaller version of the problem, then combines it with the current step
Without a reachable base case → infinite recursion → StackOverflowError

factorial(1) → returns 1

factorial(2) → 2 × factorial(1)

factorial(3) → 3 × factorial(2)

Each call waits on the stack until the base case returns, then results combine going back up.

2 CLASSIC EXAMPLES: FACTORIAL & FIBONACCI

static long factorial(long n) { if (n <= 1) return 1; // base case return n * factorial(n - 1); // recursive case }

static long fibonacci(long n) { if (n == 0 || n == 1) return n; // base cases return fibonacci(n-1) + fibonacci(n-2); }

3 RECURSION vs. ITERATION

Recursion

Often more readable for naturally recursive problems (trees, divide-and-conquer)
Uses call-stack memory — can overflow for deep recursion

Iteration

Usually faster & uses constant extra memory
Can be less intuitive for problems that are naturally recursive

4 TOWERS OF HANOI

static void hanoi(int n, String from, String to, String via) { if (n == 0) return; hanoi(n-1, from, via, to); System.out.println("Move disk "+n+" from "+from+" to "+to); hanoi(n-1, via, to, from); }

Idea

Move n disks from one peg to another (using a third as helper), never placing a larger disk on a smaller one — a textbook example of elegant recursive thinking, needing 2ⁿ − 1 moves.

5 FRACTALS & RECURSIVE BACKTRACKING

Fractals

Self-similar patterns (e.g. the Koch snowflake) generated by recursively applying the same drawing rule to smaller and smaller pieces.

Backtracking

Recursively try a choice, and if it leads to a dead end, undo it and try the next option — used for puzzles like mazes, Sudoku, or the N-Queens problem.

6 BIG O NOTATION — MEASURING EFFICIENCY

Notation	Name	Example
`O(1)`	Constant	array access by index
`O(log n)`	Logarithmic	binary search
`O(n)`	Linear	scanning a list once
`O(n log n)`	Linearithmic	efficient sorts (merge/quick sort)
`O(n²)`	Quadratic	nested loop over the same data
`O(2ⁿ)`	Exponential	naive recursive Fibonacci

Why it matters

Big O describes how an algorithm's running time (or memory) grows as input size n grows — it's about scalability, not exact runtime, and helps compare algorithms independent of hardware.