Recursion can produce concise, clear algorithms for problems that repeatedly divide into smaller versions of themselves. However, recursive solutions can be less memory-efficient, slower, and more difficult to trace than equivalent iterative solutions.
A recursive algorithm contains a base case, which terminates the process, and a recursive case, which calls the same subprogram with a reduced or simplified input. Without a reachable base case, recursion continues until an error occurs.
For example, factorial can be defined as:
Calling factorial with creates calls for , , , and . Each call is stored in a stack frame on the call stack until the base case is reached; the calls then return in reverse order.
| Advantages | Limitations |
|---|---|
| Often produces shorter, more readable code for naturally recursive structures such as trees. | Every call requires a stack frame, increasing memory use. |
| Matches recursive problem definitions directly, such as factorial and tree traversal. | Excessive recursion can cause stack overflow when the call stack has insufficient space. |
| Supports divide-and-conquer algorithms by reducing a problem into smaller subproblems. | Repeated subproblems may cause poor time efficiency unless results are stored using memoization. |
| Can simplify algorithms that would otherwise require a manually managed stack. | Recursive calls introduce processing overhead and may be harder to trace or debug. |
A common misconception is that recursion is always faster because it uses fewer lines of code. Code length does not determine efficiency: an iterative solution may use less memory and avoid repeated subprogram-call overhead.
Exam technique: For a command term such as compare or evaluate, discuss both readability and resource use. Identify the base case, explain how inputs progress toward it, and refer explicitly to call-stack memory; do not merely state that recursion “repeats itself.”
