(A Level) Recursion

Learning objectives

Define a recursive routine as one that calls itself, and identify the base case and the general case in a given recursive definition

Trace the execution of a recursive routine such as a factorial, a Fibonacci term or a binary search, showing each call made and the value it returns

Explain how the call stack stores the return address, the parameters and the local variables of every call, and describe what causes stack overflow when a base case is never reached

Rewrite a simple recursive routine as an iterative one and an iterative routine as a recursive one, and compare the two versions on readability, memory use and speed

Use recursion where it matches the structure of the data, for example when traversing a binary tree or working through a nested list, and justify that choice