Recursion in F#

Our example demonstrates recursive functions in F#. Here’s a classic implementation of factorial:

open System

let rec fact n =
    if n = 0 then 1
    else n * fact (n - 1)

[<EntryPoint>]
let main argv =
    printfn "%d" (fact 7)
    
    // F# doesn't have the concept of closures in the same way as some other languages,
    // but we can define local functions which can be recursive
    let rec fib n =
        if n < 2 then n
        else fib (n - 1) + fib (n - 2)
    
    printfn "%d" (fib 7)
    0 // return an integer exit code

This fact function calls itself until it reaches the base case of fact 0.

In F#, we use the rec keyword to define recursive functions. This is required for the compiler to allow the function to call itself.

For the Fibonacci sequence, we define a local function fib inside the main function. This local function can also be recursive, again using the rec keyword.

To run this program, save it as Recursion.fs and use the F# compiler:

$ fsharpc Recursion.fs
$ mono Recursion.exe
5040
13

F# is typically used within the .NET ecosystem, so you might also compile and run it using the .NET CLI:

$ dotnet fsi Recursion.fs
5040
13

This example demonstrates how F# handles recursion, both in top-level functions and in locally defined functions. The syntax and structure are quite different from imperative languages, showcasing F#’s functional programming paradigm.