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

OCaml, lesson 5

Loops and recursion

Sooner or later you need to do something many times: count down, add up a list of numbers, read input until it runs out. OCaml has classic loops, but most OCaml code repeats work with recursion: a function that calls itself.

for loops

A for loop counts through a range of integers. Both ends are included:

Use downto to count backwards: for i = 10 downto 1 do ... done. If the start is already past the end (say for i = 1 to 0), the body never runs. The body must return unit, so it is the place for printing and other side effects.

OCaml also has while cond do ... done, but since bindings cannot change, a while loop needs a mutable reference to ever stop. There is also no break or . These loops fit imperative code; for everything else, recursion is simpler.

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.

continue

Recursion

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

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

Each call works on a smaller n, so it always reaches the base case. Forget the base case and the function calls itself forever.

Carrying a result: accumulators

To compute something while repeating, pass the result so far as an extra argument, usually called an accumulator:

Notice that the recursive call is the very last thing the function does. This is called a tail call, and OCaml turns it into a plain jump, so the function runs in constant memory no matter how many times it repeats. Writing loops this way is safe even for millions of steps.

Early exit

Stopping early is natural with recursion: you simply do not make the next call. Here is a loop that reads lines until it sees stop:

Once the "stop" case returns, the remaining input is never read. That is the recursive version of break.

Further reading

  • Loops and Recursion
  • The OCaml manual: control structures

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.

Sample input:

Sample output:

let () =
  for i = 1 to 3 do
    Printf.printf "Lap %d\n" i
  done
let rec countdown n =
  if n = 0 then print_endline "Go!"
  else begin
    Printf.printf "%d\n" n;
    countdown (n - 1)
  end

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

let () = Printf.printf "%d\n" (sum_to 100 0)   (* 5050 *)
let rec read_until_stop count =
  match read_line () with
  | "stop" -> count
  | _ -> read_until_stop (count + 1)
3
3
2
1
Liftoff!
12
5
8
0
25