Worked question 5 - A Level Paper 1: Algorithms and Data Structures
A recursive function to compute factorial(n) calls itself n times before returning, with each call adding a new stack frame.
An iterative version uses a single loop and one accumulator variable.
State the space complexity of each version, in terms of n, and explain the difference. Use auxiliary space, assume fixed-size arithmetic, and assume recursive stack frames are retained without tail-call elimination.
Answer
Recursive: O(n) because each call adds a stack frame; iterative: O(1) because it reuses the same variables
Mark scheme
| B1 | for stating the recursive version has space complexity O(n) |
| B1 | for explaining this is because each recursive call adds a stack frame that remains until the call returns |
| B1 | for stating the iterative version has space complexity O(1) |
| B1 | for explaining this is because it reuses the same variables on each loop iteration rather than growing the call stack |





