Tracing Recursive Algorithms
- Tracing a recursive algorithm involves following each function call to understand how the algorithm progresses and eventually reaches a solution.
- This process is crucial for debugging and gaining insight into the algorithm's behaviour.
Hint
Tips for tracing recursive algorithms:
- Draw the Call Stack: Visualise each recursive call.
- Write down/draw each function call and its return value.
- This will help you see the overall structure and flow of the algorithm.
- Identify the Base Case: Ensure you know when the recursion stops and what value is returned.
- Track Return Values: Pay attention to how return values are combined to form the final solution.
Example: Factorial Calculation
Consider the following recursive algorithm to calculate the factorial of a number $n$:
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(3))
Let's trace factorial(3):
- Call: factorial(3)
- Condition: n != 0 and n != 1
- Action: return 3 * factorial(2)
- Call: factorial(2)
- Condition: n != 0 and n != 1
- Action: return 2 * factorial(1)
- Call: factorial(1)
- Condition: n == 1
- Return: factorial(1) = 1
- Return: factorial(2) = 2 * 1 = 2
- Return: factorial(3) = 3 * 2 = 6
Hint
Often it's easier to trace an algorithm in the form of a table:
| Steps | Call | Variable value | Condition checked | Action Taken | Return Value |
|---|---|---|---|---|---|
| 1 | factorial(3) | n=3 | n ≠ 0 and n ≠ 1 | Calls factorial(2) | - |
| 2 | factorial(2) | n=2 | n ≠ 0 and n ≠ 1 | Calls factorial(1) | - |
| 3 | factorial(1) | n=1 | n = 1 (base case) | Returns 1 | 1 |
| 4 | factorial(2) | n=2 | - | Returns 2 × factorial(1) = 2 × 1 | 2 |
| 5 | factorial(3) | n=3 | - | Returns 3 × factorial(2) = 3 × 2 | 6 |
Common Mistake
Common mistakes:
- Ignoring the Base Case:
- Failing to identify or understand the base case can lead to infinite recursion.
- Always start by identifying the base case and ensure it is reached in your trace.
- Misunderstanding the Call Stack:
- Each recursive call has its own execution context.
- Local variables in one call do not affect those in another.
- Overlooking Return Values:
- Ensure you track the return value of each recursive call, as it often contributes to the final solution.
Example: Traversing Data Structures
Recursive algorithms are often used to traverse complex data structures like binary trees.
Consider a binary tree and a recursive algorithm to perform an in-order traversal.
Note
Inorder traversal visits nodes in the order: left subtree, current node, right subtree. This pattern is crucial for understanding the algorithm's behavior.
| Step | Current Call | Action Taken | Output |
|---|---|---|---|
| 1 | inorderTraversal(A) | Call inorderTraversal(B) | - |
| 2 | inorderTraversal(B) | Call inorderTraversal(D) | - |
| 3 | inorderTraversal(D) | Output D | D |
| 4 | inorderTraversal(B) | Output B | B |
| 5 | inorderTraversal(B) | Call inorderTraversal(E) | - |
| 6 | inorderTraversal(E) | Output E | E |
| 7 | inorderTraversal(A) | Output A | A |
| 8 | inorderTraversal(A) | Call inorderTraversal(C) | - |
| 9 | inorderTraversal(C) | Output C | C |
Self review
- How does the call stack help you understand the flow of a recursive algorithm?
- What are the common pitfalls when tracing recursive algorithms, and how can you avoid them?
- Try to practise tracing:
- Fibonacci Sequence: Trace a recursive algorithm that calculates the 5th Fibonacci number.
- Towers of Hanoi: Trace the recursive solution to this classic problem with 4 discs, focusing on the movement of disks between rods.
