Higher Level only (B2.4.4 and B2.4.5). Recursion is when a function calls itself to solve a problem by breaking it into smaller versions of the same problem. This unit explains the base case and the recursive case, how the call stack works, how recursion compares with using a loop, and how to trace a simple recursive function such as factorial.
Slide 1 / 4
What is recursion?
Recursion is when an algorithm (a function or method) calls itself with updated parameters until it reaches a stopping condition called the base case.
Every recursive solution needs two parts: the base case, which stops the recursion and returns a value directly, and the recursive case, which calls the function again on a smaller version of the problem.
Without a correct base case the function would call itself forever, filling up memory and causing a stack overflow that crashes the program.
Recursion suits problems that can be broken into smaller versions of themselves, such as calculating a factorial or working through a tree.
Check you've got it
0/4
1. What is the purpose of the base case in a recursive algorithm?
2. Given factorial(n) returns 1 when n <= 1, and otherwise returns n * factorial(n - 1), what value does factorial(4) return?
3. Why does deep recursion use more memory than an equivalent loop?
4. A recursive function natural(n) returns 1 when n <= 1, and otherwise returns n + natural(n - 1). What does natural(4) return?
Free revision content. Multiple-choice answers are marked instantly. Written answers are marked by AI on /free-mark.