๐ Tail Call Optimisation (TCO)
Tail Call Optimisation is a compiler/runtime technique that transforms certain recursive calls into constant-space operations. It allows deep recursion without stack overflow by reusing the current stack frame when the recursive call is the final action.
๐ง Core Concept
๐งฉ Tail Call
A tail call occurs when a function calls another (or itself) as its last operation, with no further computation afterward.
(define (fact-tail x acc)
(if (= x 0)
acc
(fact-tail (- x 1) (* x acc))) ; โ
Tail call
)๐งฉ Optimization Mechanism
- Normally, each recursive call adds a new stack frame.
- With TCO, the compiler reuses the current frame:
- Updates parameters
- Jumps to the start of the function
- No need to preserve the callerโs frame
โ๏ธ Requirements for TCO
| Condition | Must Be Met for TCO |
|---|---|
| Recursive call is last action | โ Yes |
| No computation after call | โ Yes |
| No need to return to caller | โ Yes |
| Language/compiler supports TCO | โ Yes |
๐งฉ Benefits
- Space Efficiency: Reduces space complexity from O(n) to O(1)
- Performance: Avoids stack management overhead
- Safety: Prevents stack overflow in deep recursion
- Functional Elegance: Enables recursion-heavy logic without imperative loops
๐ซ Limitations
- Not supported in all languages (e.g. Python, Java)
- Debugging becomes harder (stack trace is flattened)
- Only applies to tail calls, not general recursion
Last updated on