Recursion as Iteration
You'll learn how to replace traditional loops with recursive function calls to process collections and solve problems in a functional style.
In functional programming, recursion serves as the primary looping mechanism. Instead of using for or while loops that mutate counter variables, you call a function from within itself, passing updated parameters with each call. Each recursive call represents one "iteration" of what would traditionally be a loop cycle.
The Core Idea
Think of recursion like flipping through pages in a book: an imperative loop says "turn to page 1, then page 2, then page 3..." by updating a counter. Recursion says "read this page, then read the rest of the book"—each time you "read the rest," you're making the same decision with a smaller problem.
When processing collections recursively:
- Base case: What happens when the collection is empty? Return a default value.
- Recursive case: Process the first element, then recursively handle the remaining elements.
Example Pattern
To sum a list imperatively, you'd loop with an accumulator variable. Recursively:
sum(empty_list) = 0
sum(list) = first_element + sum(rest_of_list)
This replaces the loop counter and mutable accumulator with function parameters that change with each call. No variables are reassigned—each call receives fresh, immutable inputs.
Why This Matters
Recursion as iteration aligns with pure functional principles: no mutable state, no side effects. Each "iteration" is an independent function call with its own parameters. This makes reasoning about correctness easier and enables optimizations like tail-call elimination (though that's a future topic).
Key Takeaway: In functional programming, recursion replaces loops—each recursive call acts as one iteration, processing part of the problem and delegating the rest to the next call without mutating state.