Problems are best solved with recursion when they can be divided into smaller instances of the same problem and eventually reach a simple stopping condition. Fractals and binary trees fit this pattern naturally, although recursion is not automatically the most efficient approach.
A recursive algorithm requires two essential components:
- A base case, which stops further recursive calls.
- A recursive case, which reduces the problem and calls the same algorithm again.
Each recursive call creates a new frame on the call stack, storing parameters, local variables, and the return address. If no base case is reached, the program may cause a stack overflow.
| Problem type | Why recursion is suitable | Typical base case |
|---|---|---|
| Fractal generation | Each part repeats the same pattern at a smaller scale. | Stop when depth is zero or size reaches a minimum. |
| Binary tree traversal | Every subtree is itself a binary tree. | Stop when the current node is null. |
| Divide-and-conquer algorithms | Input is split into smaller subproblems of the same form. | Stop for one element or an empty search interval. |
For example, a recursive preorder traversal is:
PREORDER(node)
if node is not null then
output node.data
PREORDER(node.left)
PREORDER(node.right)
This visits the root, then the left subtree, then the right subtree. Moving output node.data produces inorder or postorder traversal.
A common misconception is that recursion is always faster than iteration. Recursion can make self-similar or hierarchical algorithms clearer, but it adds call-stack overhead and may repeat calculations unless memoization is used.
For IB Computer Science B2.4, be ready to trace recursive calls in a trace table, identify the base and recursive cases, and explain why a binary tree or fractal has a recursive structure. In an exam response, mention termination and stack usage, then compare recursion with an iterative alternative when asked to evaluate suitability.
