Tail recursion is recursion where the recursive call is the function’s final computation: its result returns directly, without further manipulation. This lets recursive loops run without growing the stack. section 2.7
The usual pattern moves unfinished work into parameters. An accumulator or carried-forward state records what earlier recursive calls would otherwise need to do after returning, so the next call can finish the computation directly. section 2.7 section 6.8
A tail-recursive loop typically follows these steps:
- Define a local recursive helper with parameters for the remaining work and accumulated or current results. section 2.7
- Stop at a base case and return the accumulated result. section 2.7 section 6.8
- Otherwise, update the state and make the recursive call as the entire returned expression. section 2.7 section 2.7
Fibonacci with carried state
The helper tracks the remaining count, the current Fibonacci number, and the next one. Each call shifts next into current and computes a new next, avoiding deferred additions after recursion. section 2.7
def fib(n: Int): Int =
@annotation.tailrec
def go(n: Int, current: Int, next: Int): Int =
if n <= 0 then current
else go(n - 1, next, current + next)
go(n, 0, 1)
Inspect a complete Scala implementation: the recursive call is the final expression, and @annotation.tailrec marks the intended optimization. section 2.7
def isSorted[A](as: Array[A], gt: (A,A) => Boolean): Boolean =
@annotation.tailrec
def loop(n: Int): Boolean =
if n + 1 >= as.length then true
else if gt(as(n), as(n + 1)) then false
else loop(n + 1)
loop(0)
Compare the same loop shape in isSorted, where the helper advances an array index and terminates at the final adjacent pair. section 2.7
