Since loops rely on mutable state, functional programming replaces them with recursion, in which a function calls itself on smaller subproblems until it reaches a base case. Deep recursion, however, can overflow the call stack. Tail call optimization solves this by reusing the current stack frame when a function call is in tail position, the last operation before returning. Languages like Haskell, Scheme, and Erlang perform TCO automatically, and trampolining achieves the same effect in strict languages by returning thunks that a loop repeatedly invokes until a final value is reached.
Folds are the workhorses of functional iteration. The reduce, or fold, operation combines all elements of a collection into a single value using an accumulator function and an initial value. There are two main variants: a left fold processes elements from left to right and is naturally tail-recursive, while a right fold processes from right to left, builds a chain of thunks, and can be lazy on infinite lists. The strict left fold \( \text{foldl}' \) forces the accumulator at each step to prevent the buildup of unevaluated thunks that \( \text{foldl} \) would otherwise accumulate, which is essential for constant-space numerical sums. The most general fold is \( \text{foldMap} \): it maps each element to a monoid value and combines them, so that \( \text{sum} \) is \( \text{foldMap Sum} \) and \( \text{length} \) is \( \text{foldMap}(\_ \mapsto \text{Sum } 1) \). Unfold, the dual of fold, builds a data structure from a seed by repeatedly producing a new element and the next seed, enabling the generation of sequences and streams without explicit mutation. A stream is a lazy, possibly infinite sequence that supports bounded-memory processing of unbounded data through take, map, and filter; this contrasts with iterators, which pull values on demand and signal termination explicitly, while streams push values through a composable pipeline.
Evaluation strategies determine when expressions are actually computed. Eager, or strict, evaluation, used by languages like JavaScript, Python, and Java, evaluates expressions as soon as they are bound to a variable, which is predictable but may compute values that are never used. Lazy, or non-strict, evaluation, used by Haskell by default, delays computation until the value is actually needed, enabling infinite data structures, avoiding unnecessary work, and improving performance when only part of a result is required. Thunks are zero-argument functions that wrap an unevaluated expression; they are the mechanism behind lazy evaluation in strict languages and are used in Redux middleware. Thunk leaks occur when unevaluated thunks accumulate in memory because the surrounding structure is referenced, requiring profiling tools to diagnose. Memoization caches the results of expensive pure function calls so that repeated calls with the same arguments return instantly, and the monoid laws — associativity of the binary operation and the existence of an identity element — guarantee that folds and aggregations behave predictably and can be parallelized safely.