Definition
Recursion is a programming technique where a function calls itself in order to solve a problem. This continues until a base condition is met, at which point the recursion halts and the stack unwinds.
Advantages and Disadvantages
Pros & Cons
Pros & Cons (Recursion):
| Advantages | Disadvantages |
|---|---|
| Simplifies code for naturally recursive problems (factorials, Fibonacci) | Memory-intensive (each call adds a frame to the call stack) |
| Often results in more elegant, readable solutions | Risk of stack overflow with deep recursion |
| Fewer lines of code compared to iterative solutions | Debugging can be challenging |
| Direct translation of mathematical definitions | May be slower than iteration due to function call overhead |
Worked Example
Recursion Example: Factorial
Unwinding result: 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24
Recursive vs Iterative:
pseudocode
function factorial(n):
if n == 0 OR n == 1 then
return 1
end if
return n * factorial(n - 1)
end function
| Call | Expansion |
|---|---|
| factorial(4) | 4 × factorial(3) |
| factorial(3) | 3 × factorial(2) |
| factorial(2) | 2 × factorial(1) |
| factorial(1) | 1 (base case) |
Recursive vs Iterative:
pseudocode
// Recursive Fibonacci
function fibRecursive(n):
if n <= 1 then
return n
end if
return fibRecursive(n-1) + fibRecursive(n-2)
end function
// Iterative Fibonacci
function fibIterative(n):
if n <= 1 then
return n
end if
a = 0
b = 1
for i = 2 to n:
temp = a + b
a = b
b = temp
end for
return b
end function
Recursion Compared with Iteration
Key Point
| Feature | Recursion | Iteration |
|---|---|---|
| How it repeats | The subroutine calls itself with a smaller version of the problem | A loop repeats a block of code |
| How it stops | A base case returns a value without making another call | The loop condition is no longer met, or the count is reached |
| Memory | Every call adds a frame to the call stack holding its parameters, local variables and return address | The same variables are reused, so memory use does not grow |
| Risk | Stack overflow if the base case is never reached or the recursion is too deep | An infinite loop if the condition never changes |
| Code | Often shorter and closer to the way the problem is defined | Often longer, but usually faster and easier to trace |
Any algorithm written with recursion can be rewritten with iteration, and the other way round. When the last call reaches the base case, the calls return in reverse order as their frames are removed from the stack: this is the stack unwinding.