Recursion as F#'s Default Loop
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.
Cricket analogy: A commentator describing a partnership as 'today's score is yesterday's score plus today's runs' is thinking recursively, defining the current total in terms of a smaller, prior total, just as factorial n is defined in terms of factorial (n-1).
Anatomy of a Recursive Function
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.
Cricket analogy: Umpires signal 'over' after exactly six legal balls — a fixed stopping condition — the same way a recursive function needs a base case like n <= 1 to guarantee the recursion eventually stops.
// Non-tail-recursive factorial: work happens AFTER the recursive call returns
let rec factorial n =
if n <= 1 then 1
else n * factorial (n - 1) // multiplication happens after the call
// Tail-recursive version using an accumulator
let factorialTail n =
let rec loop acc n =
if n <= 1 then acc
else loop (acc * n) (n - 1) // the recursive call IS the return value
loop 1 n
printfn "%d" (factorial 10) // 3628800
printfn "%d" (factorialTail 100000) // runs in constant stack spaceTail Calls and Stack Safety
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.
Cricket analogy: A fielder who throws directly to the keeper with no further action needed afterward completes their part of the play in one motion, just as a tail call completes a function's job with no pending work left afterward.
Rewriting for Tail Recursion
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.
Cricket analogy: A scorer who updates the running total on the scoreboard after every single ball, rather than waiting until the innings ends to add everything up, carries the accumulator forward exactly like acc carries the running product forward in factorialTail.
You can confirm a function is genuinely tail-recursive by inspecting the compiled IL for a .tail prefix on the call instruction (tools like ILSpy or dotnet-ildasm will show it), or more practically, by testing it against a large input — a properly tail-recursive factorialTail 1000000 should run without a StackOverflowException, while the naive version will not.
Not every recursive call that looks tail-positioned actually is one under .NET's rules — calls inside a try/with or try/finally block are never true tail calls, because the runtime must keep the frame alive to handle a possible exception, so wrapping recursive logic in exception handling silently defeats tail-call optimization.
- F# uses recursion, marked with the rec keyword, as its primary tool for repeating work instead of mutable loop counters.
- Every correct recursive function needs a base case that stops the recursion and a recursive case that makes measurable progress toward it.
- A tail call is a recursive call that is the very last action in a function, with no pending work after it returns.
- Tail-call optimization lets the .NET runtime reuse the current stack frame instead of growing the stack, enabling constant stack space.
- The accumulator pattern converts non-tail-recursive functions into tail-recursive ones by carrying the running result as an extra parameter.
- Non-tail-recursive functions risk StackOverflowException on large or unbounded inputs.
- Recursive calls inside try/with or try/finally blocks are never optimized as true tail calls.
Practice what you learned
1. What keyword does F# require for a function to call itself?
2. Why is `let rec factorial n = if n <= 1 then 1 else n * factorial (n - 1)` NOT tail-recursive?
3. What is the purpose of the accumulator parameter in a tail-recursive rewrite?
4. Which situation prevents a recursive call from being optimized as a true tail call under .NET?
5. What happens if a recursive function lacks a proper base case?
Was this page helpful?
You May Also Like
Higher-Order Functions in F#
Learn how F# treats functions as first-class values that can be passed as arguments, returned as results, and composed to build powerful, reusable data transformations.
Pipelining and Composition
Master F#'s |> pipe operator and >> / << composition operators to chain transformations into clear, left-to-right data pipelines.
Active Patterns
Learn how F#'s active patterns let you define custom, named ways to pattern-match against values, from simple classification to parsing and matching against external data.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics