Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 37 ยท Functions and Pipelines

Recursion in F#: rec, Tail Calls, Accumulators and Mutual Recursion

Write recursive functions in F#: base case and recursive case, accumulator style, tail-call optimisation, avoiding stack overflow, mutual recursion with and, and when to prefer List.fold.

With immutable values and no loops-with-counters, recursion is how functional programmers repeat work. A recursive function solves a problem by calling itself on a smaller piece. It sounds exotic but follows a simple pattern: a base case that stops, and a recursive case that moves toward it. This lesson shows the basic shape, the efficient tail-recursive form, accumulators, mutual recursion, and when a library function is the better choice.

The shape

A function that calls itself must be declared with rec:

FSHARP
let rec factorial n =
    if n <= 1 then 1
    else n * factorial (n - 1)

factorial 5        // 120
  • Base case: n <= 1 returns 1 without recursing.
  • Recursive case: n * factorial (n - 1) reduces the problem.

If the base case is missing or never reached, the function recurses until the stack overflows. Always ask: "does every call get closer to the base case?"

FSHARP
let rec sumTo n =
    if n = 0 then 0 else n + sumTo (n - 1)

sumTo 4       // 4 + 3 + 2 + 1 + 0 = 10

Recursion on lists

Lists are built for recursion. A list is either empty ([]) or a head followed by a tail (head :: tail). Matching on those two shapes gives you a template for almost every list function:

FSHARP
let rec length list =
    match list with
    | [] -> 0
    | _ :: tail -> 1 + length tail

let rec sum list =
    match list with
    | [] -> 0
    | head :: tail -> head + sum tail

sum [ 1; 2; 3 ]      // 6

The match expression is covered later; read | [] -> as "if the list is empty" and head :: tail as "otherwise split off the first item".

The stack and why it matters

Each call of sumTo waits for the result of the next one before adding, so 100000 nested calls pile up on the call stack:

TEXT
sumTo 3 = 3 + sumTo 2
            = 3 + (2 + sumTo 1)
              = 3 + (2 + (1 + sumTo 0))

A very large input causes a StackOverflowException, which cannot be caught and ends the process. The cure is a tail-recursive version.

Tail recursion with an accumulator

A call is in tail position when it is the very last thing the function does: nothing is left to do with its result. The F# compiler turns tail calls into a jump, so they use constant stack space, exactly like a loop. To get there, carry the partial answer along in an accumulator parameter:

FSHARP
let sumToTail n =
    let rec loop i acc =
        if i = 0 then acc
        else loop (i - 1) (acc + i)
    loop n 0

sumToTail 10           // 55

With an int the total of a very large range would wrap around, so the int64 version below is safer. The inner loop is the recursive worker; the outer function exposes a nice signature and hides the accumulator.

FSHARP
let sumToBig (n: int64) =
    let rec loop i acc =
        if i = 0L then acc
        else loop (i - 1L) (acc + i)
    loop n 0L

sumToBig 1_000_000L    // 500000500000L

Pattern recap:

  1. Create an inner loop with an extra acc parameter.
  2. The base case returns acc.
  3. The recursive case calls loop with updated arguments as its last action.

Compare factorial in tail form:

FSHARP
let factorialTail n =
    let rec loop i acc =
        if i <= 1 then acc else loop (i - 1) (acc * i)
    loop n 1

n * factorial (n - 1) is not a tail call: after the recursive call returns, the multiplication still has to run. The same goes for 1 + length tail. Tail position means the call is the final operation.

Building lists recursively

When you build a list with an accumulator, items end up reversed, because you prepend with :: (fast, O(1)). Reverse at the end:

FSHARP
let squares n =
    let rec loop i acc =
        if i = 0 then acc
        else loop (i - 1) ((i * i) :: acc)
    loop n []

squares 4         // [1; 4; 9; 16]

Here counting down while prepending gives the list in the right order for free.

Mutual recursion

Two functions that call each other must be defined together with and:

FSHARP
let rec isEven n =
    if n = 0 then true else isOdd (n - 1)
and isOdd n =
    if n = 0 then false else isEven (n - 1)

isEven 10     // true

Without and, isEven could not see isOdd, because F# reads definitions top to bottom.

Trees and branching recursion

Some structures branch, so the function recurses more than once. Fibonacci is the classic example:

FSHARP
let rec fib n =
    if n < 2 then n else fib (n - 1) + fib (n - 2)

This is simple but exponentially slow for large n, because it recomputes the same values. An accumulator version needs only two carried values:

FSHARP
let fibFast n =
    let rec loop i a b =
        if i = 0 then a else loop (i - 1) b (a + b)
    loop n 0 1

fibFast 10    // 55

When not to write recursion by hand

Common patterns are already in the library: List.sum, List.fold, List.map, List.rev, List.unfold. Use a hand-written recursive function when the shape is unusual (walking a tree, parsing, state machines). Reach for List.fold when you are just combining items:

FSHARP
let sum = List.fold (+) 0 [ 1; 2; 3 ]      // 6

Run it: C# stand-ins

C# does not guarantee tail-call elimination, so deep recursion there can overflow the stack; typical C# code uses loops for the accumulator version. These stand-ins compute the same numbers.

C# C# stand-in: factorial and Fibonacci

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

C# C# stand-in: sum of a list recursively

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What two parts does every recursive function need?

    The base case stops the recursion; the recursive case reduces the problem.
  2. 2. Which keyword lets a function call itself?

    Use let rec for recursive functions.
  3. 3. Is n * factorial (n - 1) a tail call?

    A tail call is the final action; here the multiply comes afterward.
  4. 4. What is the purpose of an accumulator parameter?

    Accumulators turn a growing call stack into constant-space tail recursion.
  5. 5. How do you define two functions that call each other?

    and makes the definitions mutually visible.

Summary

  • Recursive functions need rec, a base case and progress toward it.
  • Lists decompose as [] or head :: tail, which suits recursion.
  • Tail calls (the last action) run in constant stack space; use accumulator parameters and an inner loop.
  • Mutually recursive functions use let rec ... and ....
  • Prefer library functions such as List.fold for common patterns.

Next: Lambdas and higher-order functions