Recursion: Functions That Call Themselves

Factorial of 5 is 5 times factorial of 4. Factorial of 4 is 4 times factorial of 3. The pattern repeats until factorial of 1, which is defined as 1. That bottom definition is the base case.

Each call waits for a smaller call to finish. The call stack remembers where to resume. Too many calls without a base case overflow the stack.

Watch the step-flow animation. See factorial(4) peel down to 1, then multiply on the way back up.

Backtracking in the maze lab was recursion in disguise: try a path, undo, try another. Tree traversals call left and right subtrees the same way.

Board exam questions often ask trace this recursive function. Write stack frames on paper.

Binary search is iterative in our lab, but its divide-half idea pairs naturally with recursive thinking too.

Naive Fibonacci recursion recomputes the same values many times. That waste sets up the next topic: remember answers you already calculated.

Recursion is not always the fastest tool, but it is often the clearest way to state a problem.

Next: memoisation turns repeated subproblems into a table lookup.