Unit 2.4

RECURSION
THEORY

To understand recursion, you must first understand recursion. It is the art of solving a large problem by solving smaller instances of the same problem.

F(n) = F(n-1) + F(n-2)

The Infinite Mirror.

The Stack

The Tower of Hanoi is the quintessential recursive problem. It cannot be solved easily with loops, but with recursion, the logic is elegant: Move $n-1$ disks out of the way, move the bottom disk, then move $n-1$ disks back on top.

Recursive Problem

Tower of Hanoi

Moves: 0

Move all disks to Tower 3.

The Base Case

Base Case

CODE

The stopping condition. Without this, the recursion continues forever (Infinite Loop) until the program crashes.

if (n === 0) return;

Recursive Step

CODE

The part of the function where it calls itself with a modified (usually smaller) input.

return n * factorial(n - 1);

Call Stack

CODE

The memory structure that tracks active subroutines. Recursion pushes new layers onto the stack until the base case is reached.

Stack Overflow

Memoization

CODE

Optimization technique. Storing the results of expensive function calls so you don't have to recalculate them (e.g., caching Fibonacci numbers).

cache[n] = result;

The Fibonacci Sequence (Recursive Growth)

0→1→1→2→3→5→8→13→21→34→55→89...