<aside> 📚

L4: Recurse! covers what recursion is, its structure (base case + recursive clause), the connection to induction, programming recursively in Java (factorial, integer powers with fast exponentiation, GCD via Euclid's algorithm), helper functions for efficiency, the cost of recursion, when not to recurse (Fibonacci), and the analysis of recursive algorithms (factorial, power, Towers of Hanoi).

</aside>

📋 At a Glance

• [ ] Understand the structure of recursion (base case + recursive clause)
• [ ] Relate recursion to proof by induction
• [ ] Implement factorial, power, and GCD recursively in Java
• [ ] Use helper functions to improve recursive efficiency
• [ ] Know the cost of recursion (stack overhead) and when to unroll
• [ ] Know when NOT to recurse (overlapping subproblems, e.g. Fibonacci)
• [ ] Analyse recursive algorithms: derive and solve recurrences for T(n)
• [ ] Understand Towers of Hanoi: algorithm, optimality proof, and T(n) = 2^n - 1

<aside> 📅

Week 2 (w/c 2 Feb) — Lecture 4 of 26 | Tutorial 2 applies (same as L3)

</aside>

<aside> 💡

Key principle: Recursion reduces a problem to one or more smaller problems of the same type until a trivial base case is reached. It is the mirror image of induction — recursion defines things, induction proves things about them. Always start with the base case.

</aside>

1. What Is Recursion?

Recursion is a strategy where we reduce solving a problem to solving one or more smaller problems of the same type, repeating until we reach a trivial case.

• Can be used to define functions using references to themselves
• Can be used to write algorithms that call themselves on smaller inputs

Example — factorial:

$n! = n \times (n-1)!$ with $0! = 1$