Recursion — common mistakes

In Paper 4, you might be asked to trace a recursive function's execution and show the final return value. A good technique is to write down the chain of calls as shown in the factorial example, keeping track of the parameters at each step. Then, work your way back up the chain as the function returns, calculating the result at each level.

In terms of raw speed and memory, usually yes. The overhead of managing the call stack for each function call makes recursion slower and more memory-intensive than a simple loop. However, for some complex algorithms, a recursive solution is so much simpler to write and maintain that it's the preferred choice. Also, some compilers can perform 'tail call optimisation' to make certain types of recursion as efficient as iteration.

Several reasons. Firstly, some problems are fundamentally recursive, and thinking about them recursively is the most natural approach (e.g., file system traversal, parsing programming languages). Secondly, many important data structures, like trees and graphs, are defined recursively, and their algorithms are most elegantly expressed with recursion. It's a fundamental concept in computer science that enables a different way of thinking about problems.

Yes. If the initial input requires an extremely deep level of recursion before the base case is reached, it can still exhaust the call stack's memory. For example, calculating Factorial(1000000) would almost certainly cause a stack overflow, even though the function is logically correct.