Accumulator Pattern
Convert to tail-recursive.
The Accumulator Pattern
The accumulator pattern converts a non-tail-recursive function into a tail-recursive one. You carry the partial result in an extra parameter (the accumulator) instead of building it up after the call returns.
The Core Idea
Instead of n + sum(n-1) (work after the call), you compute the new partial total before the call: sum(n-1, acc + n). Now the recursive call is the last action.
All lessons in this course
- Recursion Basics
- The tailrec Annotation
- Accumulator Pattern
- Trampolining