Recursion expresses a loop without mutation: a function calls itself with a smaller or simpler state until a base case returns a value. section 2.7
Factorial as a functional loop
A factorial function can contain a local helper named go. Its parameters hold the remaining input and accumulated result. Each recursive call advances the state with go(n - 1, n * acc); when n <= 0, the helper returns acc without another call. section 2.3.1
def factorial(n: Int): Int =
def go(n: Int, acc: Int): Int = #1
if n <= 0 then acc
else go(n - 1, n * acc)
go(n, 1)
Read the helper as a loop: the base case exits, while the recursive branch supplies the next state. section 2.3.1
Use these checks when reading or designing a recursive function:
- Identify the state carried between calls. section 2.3.1
- Find the base case that returns without recursion. section 2.3.1
- Check whether the recursive call is in tail position, with no work left afterward. section 2.3.1
- Trace calls manually to follow evaluation and changing values. section 2.3.1
