9618 · 19.2
Recursion flashcards
Revision flashcards for Cambridge 9618 Recursion (syllabus 19.2). Flip, recall, then mark a real past-paper question.
Card
What is recursion?
A method of solving a problem where the solution depends on solutions to smaller instances of the same problem. In programming, this is achieved when a function calls itself.
Card
What are the two essential components of a recursive function?
1. A base case: The condition under which the recursion stops. 2. A recursive step: The part of the function that calls itself, typically with modified arguments that move towards the base case.
Card
What is a 'base case' in recursion?
The terminating condition that does not involve a recursive call. It's the simplest instance of the problem that can be solved directly, preventing infinite recursion.
Card
What happens if a recursive function lacks a base case, or the base case is never reached?
It results in infinite recursion, where the function keeps calling itself. This will eventually consume all available memory on the call stack, leading to a stack overflow error.
Card
What is a 'stack overflow' error?
An error that occurs when the call stack, which has a finite amount of memory, becomes full. This is a common result of infinite or very deep recursion.
Card
How does the call stack support recursion?
Each time a function is called, a new 'stack frame' containing its parameters and local variables is pushed onto the call stack. When a function returns, its frame is popped off. This LIFO (Last-In, First-Out) structure manages the state of each nested call.
Card
Compare the memory usage of recursion and iteration.
Recursion generally uses more memory than iteration. Each recursive call adds a new frame to the call stack, whereas iteration typically uses a constant amount of memory for its loop variables.
Card
When might you prefer recursion over iteration?
For problems that are inherently recursive in nature, such as tree traversals, graph algorithms (like Depth First Search), or working with fractal data. The recursive code is often more elegant and easier to understand in these cases.
Card
What is a potential disadvantage of recursion besides memory usage?
It can be slower due to the overhead of function calls (pushing/popping stack frames). For simple tasks like summing an array, an iterative loop is usually more performant.
Card
Can any recursive algorithm be implemented iteratively?
Yes, any problem that can be solved with recursion can also be solved with iteration, often by using an explicit stack data structure to mimic the call stack. However, the iterative solution may be significantly more complex to write and understand.