Learn/F#/5. Loops and recursion
Lesson 5 of 8
Sign in

F#, lesson 5

Loops and recursion

Many tasks need repetition: count down, add up prices, read input until it ends. F# has ordinary loops, and it also makes recursion (a function calling itself) easy and efficient. Idiomatic F# uses both: loops for simple side effects like printing, recursion when you are computing a result.

for loops

for ... in walks through a range or a collection. A range like 1 .. 5 includes both ends:

A range can have a step in the middle: 10 .. -1 .. 1 counts down from 10 to 1, and 0 .. 5 .. 20 gives 0, 5, 10, 15, 20. If the range is empty (like 1 .. 0), the body never runs. The body is indented under the for line.

while loops

2 exercises to try what you just read.

Exercise 1

Countdown

Press Ctrl Enter or Check to test your code.

Exercise 2

Total until zero

Press Ctrl Enter or Check to test your code.

A while loop repeats while a condition is true. Because ordinary values never change, the condition needs a mutable value to eventually become false:

F# has no break or continue. If you need to stop early, recursion is usually the cleanest answer.

Recursion

A recursive function is declared with let rec. It always has:

  1. a base case that stops, and
  2. a recursive case that does one step and calls itself with a smaller problem.

Without the base case the function would call itself forever.

Accumulators and tail calls

To compute a value while repeating, carry the result so far in an extra parameter, often called an accumulator:

The recursive call is the very last thing sumTo does. That is a tail call, and the F# compiler turns it into a plain loop, so the function uses constant memory however many times it repeats.

Early exit

With recursion, stopping early simply means not making the next call. This function reads lines until it sees stop and counts the lines before it:

Once the "stop" case returns, no more input is read. That is the functional version of break.

Further reading

  • Loops: for...in expression
  • Loops: while...do expression
  • Recursive functions: the rec keyword

Read a whole number n (0 or more). Print the numbers from n down to 1, one per line, then print Liftoff!.

Sample input:

Sample output:

A cashier types prices, one per line, and types 0 when the order is complete. Read the prices and print the total of everything before the first 0. Anything after the 0 belongs to the next customer and must be ignored. There is always a 0 in the input.

Write it as a recursive function with an accumulator.

Sample input:

Sample output:

for lap in 1 .. 3 do
    printfn "Lap %d" lap
let mutable fuel = 3
while fuel > 0 do
    printfn "Fuel: %d" fuel
    fuel <- fuel - 1
let rec countdown n =
    if n = 0 then
        printfn "Go!"
    else
        printfn "%d" n
        countdown (n - 1)

countdown 3      // 3, 2, 1, Go!
let rec sumTo n acc =
    if n = 0 then acc else sumTo (n - 1) (acc + n)

printfn "%d" (sumTo 100 0)    // 5050
let rec readUntilStop count =
    match stdin.ReadLine() with
    | "stop" -> count
    | _ -> readUntilStop (count + 1)
3
3
2
1
Liftoff!
12
5
8
0
25