Recursion and Tail Calls

F# has no built-in mutable-counter for-loop as its core repetition idiom; instead, recursion is the natural way to process data that doesn't map cleanly onto List.map or List.fold. A recursive function calls itself, and F# requires the rec keyword to allow this: let rec factorial n = if n <= 1 then 1 else n * factorial (n - 1). Without rec, F# would treat the factorial reference on the right-hand side as an undefined name, because ordinary let bindings are not visible inside their own definition. Recursion pairs naturally with F#'s algebraic data types — walking a list, a tree, or a discriminated union almost always means matching on its shape and recursing into the smaller pieces.

Every well-formed recursive function needs two things: a base case that stops the recursion, and a recursive case that makes progress toward that base case. In factorial, the base case is n <= 1, returning 1 directly with no further recursive call, and the recursive case multiplies n by the result of calling factorial on the strictly smaller value n - 1. Miss the base case, or fail to make progress toward it, and the function recurses forever — in practice, this means an eventual StackOverflowException, because each pending call consumes a frame on the call stack until the runtime runs out of space.

A call is in tail position when it is the very last thing a function does — nothing happens to its result afterward. The naive factorial above is not tail-recursive, because after factorial (n - 1) returns, the function still has to multiply that result by n; each pending multiplication keeps a stack frame alive, so factorial 100000 will overflow the stack. F# and the .NET runtime can perform tail-call optimization: when a call genuinely is in tail position, the compiler can emit a .tail IL instruction that reuses the current stack frame instead of pushing a new one, turning the recursion into something that runs in constant stack space, much like an explicit loop would.

The standard technique for making a function tail-recursive is to introduce an accumulator parameter that carries the running result forward, so the recursive call becomes the last thing that happens. factorialTail wraps a local loop function that takes acc alongside n; instead of computing n * factorial (n - 1) after the recursive call returns, it computes acc * n before making the call, so loop (acc * n) (n - 1) is now genuinely the final action. This transformation is mechanical but not free — the intermediate result now lives in a parameter that gets passed explicitly at every step, and readability can suffer slightly, which is why many F# codebases only bother with it for functions that will realistically be called on large inputs or unbounded-depth data.