Data Structures & Algorithms' own domain covered recursion and the call stack as one technique among several. Functional programming treats recursion as the PRIMARY way to express repetition — a real consequence of immutability removing the loop-counter variable most iterative loops depend on.
3 min read
# Ordinary loop — i is reassigned on every single iteration
total = 0
for i in range(5):
total += i # total is mutated repeatedly tooAn ordinary for loop works by repeatedly reassigning a counter variable (i) and an accumulator (total) — both are mutated on every pass. Lesson 2 established why mutation is something functional programming tries to avoid — and a loop counter is exactly that kind of mutable state, just so routine that it rarely gets named as such. A genuinely immutable style needs a different way to express "do this N times" that doesn't depend on reassigning anything.
def sum_to(n, acc=0):
if n == 0:
return acc
return sum_to(n - 1, acc + n) # each call gets its OWN n and acc —
# nothing is ever reassigned
sum_to(5) # 15Recursion expresses "repeat this" by having a function call itself with new argument values, rather than reassigning existing ones — each recursive call gets its own fresh n and acc, and nothing already created is ever mutated. This is Data Structures & Algorithms' own recursion-and-the-call-stack lesson's mechanism, but functional programming treats it as the default tool for repetition generally, not a specialized technique reserved for tree/graph traversal and a handful of classic problems.
Data Structures & Algorithms' own lesson already established the real risk here: every recursive call consumes actual stack memory, and a sufficiently deep recursion (without the optimization covered next) raises a genuine stack overflow — sum_to(1_000_000) would crash in ordinary Python, while the equivalent for loop runs fine, because the loop never grows the call stack at all.
def sum_to(n, acc=0):
if n == 0:
return acc
return sum_to(n - 1, acc + n) # a TAIL CALL — the recursive call is the
# VERY LAST thing this function doesA tail call is a recursive call that is the literal last operation a function performs, with nothing left to do after it returns — this specific shape means the current stack frame isn't actually needed anymore once the recursive call happens, and a compiler could reuse it instead of pushing a new one, turning the recursion into something running with the same constant stack space as an ordinary loop. Tail-call optimization (TCO) is exactly this: a language runtime recognizing this shape and performing that reuse automatically. Some functional languages (Scheme, Elixir, Haskell) guarantee TCO as part of the language specification — but Python's official interpreter deliberately doesn't implement it (a documented design decision, partly to keep stack traces fully informative for debugging), and JavaScript's spec technically allows it but almost no real engine actually implements it. In practice, this means relying on deep recursion for performance-sensitive code in either language is a real, live risk, not just a theoretical concern — sum_to(1_000_000) genuinely crashes in both, tail call or not.
Recursion remains an excellent tool for expressing naturally recursive problems clearly (tree traversal, anything Data Structures & Algorithms' own domain already covers this way) — but reaching for deep recursion purely as a stylistic substitute for an ordinary loop, in a language that doesn't guarantee TCO, trades real correctness risk (a stack overflow on sufficiently large input) for a style preference. Know which language you're in before leaning on this pattern.
Check your understanding
A quick comprehension check — not tracked, not graded, just for you.
1. Why is an ordinary loop counter considered a form of mutable state?
2. What is a tail call?
3. Why is relying on deep recursion risky specifically in ordinary Python or JavaScript?
Functional Programming Concepts