Discrete Math › Section E · Sequences › Topic E.7
Recursion and structural induction
Recursion defines a thing in terms of smaller versions of itself: a number, a set of strings, or an algorithm that calls itself. Structural induction is the matching proof method, and together they explain why recursive programs work and how long they take.
In this topic
- Defining by self-reference
- Recursively defined sets
- Structural induction
- Worked example: balanced brackets
- Recursive algorithms
- Worked example: the Towers of Hanoi
- Correctness by induction
- Worked example: the cost of naive recursion
- Recursion and iteration
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…