Course contentsShow
← Computer Science
Lesson 2135 of 2,87248. Programming ParadigmsFree lesson

Recursion as Iteration

Use recursion instead of loops to process collections and solve problems functionally.

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.