9618 · 19.2
Recursion — FAQ
Frequently asked questions for 9618 Recursion. Direct answers first, then deeper explanation — then practise with marking.
Is recursion always less efficient than iteration?
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.
Why do we learn recursion if iteration is often more efficient?
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.
Can I get a stack overflow error with a function that has a correct base case?
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.