Dive C2.05.1

From loops to recursion

The counter goes away. The function calls itself on a smaller problem.

A C# developer reaches for a loop and a counter to walk a sequence: for (int i = 0; i < n; i++), updating state as it goes. F# expresses the same repetition as a function that calls itself on a smaller input and stops at a base case. The shift is the first to make, and it comes with one rule a C# developer must know to trust it in production: a recursive call in tail position — the last thing the function does — compiles to a loop, so it runs in constant stack space. A recursion that is not in tail position builds a chain of pending work on the call stack, and on a large input that chain overflows. This dive shows the naive form, the rule, and the accumulator-passing form that makes recursion a flat loop.

Step the two forms Module hub

C2.05.1 · part 1

A loop, written as a function that calls itself

Factorial is the textbook case. In C# you loop a counter from 1 to n and multiply into a running product. In F# you say what the answer is: the factorial of n is n times the factorial of n - 1, and the factorial of 1 (or less) is 1. The keyword rec marks a function that may refer to itself; the if branch that returns 1 is the base case that ends the recursion.

let rec factorial n =        // val factorial : int -> int
    if n <= 1 then 1 else n * factorial (n - 1)

factorial 5                       // val it : int = 120

rec: marks a function that is allowed to call itself; without it, the name is not in scope inside its own body.
base case: the branch that returns without recursing — here n <= 1 -> 1 — which stops the chain.
recursive case: the branch that calls the function on a smaller input — here factorial (n - 1).

There is one detail hidden in that definition. After factorial (n - 1) returns, the function still has work to do — it must multiply the result by n. So the call is not the last action; the multiplication waits on the call stack. Each level of recursion leaves a pending multiply, and the stack grows with n. For factorial 5 that is five frames; for a few hundred thousand it is a StackOverflowException.

C2.05.1 · part 2

Tail recursion: the same loop, flat

The fix is to carry the running result down into the recursion as an extra argument — an accumulator — so that nothing waits after the recursive call. When the recursive call is the very last thing the function does, it is in tail position, and the F# compiler emits a plain loop with no new stack frame. The shape is a small inner loop that threads the accumulator and pattern-matches the list down to the empty case.

let sumTail xs =                 // val sumTail : int list -> int  (tail-recursive)
    let rec loop acc lst =
        match lst with
        | [] -> acc                // base case: the list is empty, the answer is acc
        | x :: rest -> loop (acc + x) rest   // tail call — nothing waits after it
    loop 0 xs

sumTail [1..100]                  // val it : int = 5050

The difference between the two is the position of the recursive call. In factorial the call sits inside a multiplication, so a frame must stay to finish it. In loop the call is the whole right-hand side — the new accumulator is computed first, then handed forward, and the current frame is done. That is the rule to remember: recursive call in tail position → the compiler emits a loop, and the stack stays flat.

F# does not turn every recursion into a loop — only calls in tail position. A non-tail recursion like factorial is fine for small inputs; for a large one, rewrite it with an accumulator, reach for List.fold (the next dive), or use a built-in that is already tail-recursive.

Step the call stack

Walk the two forms over a fixed input and watch the call stack. The naive factorial 5 pushes a frame for each level and holds them all open, because every frame still owes a multiply — the stack grows to its full depth before any answer comes back. The tail-recursive sumTail [1..5] keeps one frame and updates the accumulator in place — the depth never grows. Press Step to advance; the readout names the current call and the running state.

The call stack · naive grows, tail stays flat

ready · naive factorial 5

naive · factorial 5 · ready — the stack is empty. Each Step pushes one call; the multiplies wait until the base case, then unwind.

Without JavaScript: the two forms, traced by hand
form	trace	max stack depth	result
naive `factorial 5`	5·(4·(3·(2·1))) — five frames open, then unwind	5 frames	120
tail `sumTail [1..5]`	acc 0 → 1 → 3 → 6 → 10 → 15 — one frame, reused	1 frame	15

The two run the same repetition. The naive form leaves a trail of pending work the stack must hold; the tail form carries the answer forward and keeps one frame. Tail position is what makes recursion a loop.

C2.05.1 · part 3

The C# loop, beside the F# recursion

The C# loop and the tail-recursive function are two spellings of the same machine behaviour: one frame, a piece of state updated each step. C# writes the state as a mutable local; F# writes it as the accumulator argument threaded by the recursive call. The C# loop mutates acc in place; the F# loop hands a new acc to the next call. Both end in constant stack space.

C# — a loop and a mutable accumulator

int Sum(int[] xs) {
    int acc = 0;
    foreach (var x in xs)
        acc += x;                  // mutate the accumulator in place
    return acc;
}
// Sum(new[]{1,2,3,4,5}) == 15

F# — a tail-recursive accumulator loop

let sumTail xs =
    let rec loop acc lst =
        match lst with
        | [] -> acc
        | x :: rest -> loop (acc + x) rest   // hand a new acc forward
    loop 0 xs

sumTail [1..5]                    // val it : int = 15

C# habit

A for/foreach loop with a counter and a mutable accumulator — one frame, state changed in place.

F# form

A rec function with the accumulator as an argument, called in tail position — one frame, a new accumulator threaded forward.

Where this leads

Almost every accumulator loop you would write by hand is already a library function. The pattern loop acc lst = match lst with [] -> acc | x :: rest -> loop (folder acc x) rest has a name — List.fold — and it is tail-recursive for you. The next dive shows that the for-plus-mutable-accumulator is exactly fold, and that one function covers sum, maximum, count, and even building a list.

↑ C2.05 · From loops to recursion, map & fold C2.05.2 · From the accumulator loop to fold → C2.05.3 · From the transform loop to map & filter

References

Sources

Microsoft — F# functions and the rec keyword — recursive functions and tail calls.
Microsoft — F# coding conventions — guidance on recursion, accumulators, and avoiding stack overflow.
FSharp.Core API reference — List.fold and the other tail-recursive list functions.

Related in this course

C2.05.2 — From the accumulator loop to fold — the accumulator pattern, named.
C1.03 — Functions, currying & partial application — the functions a recursion is built from.
C1.07 — Collections: list, array, seq, Map & Set — the cons-list a recursive function walks.