When it gets to the head of the list (3), it recursively finds the smallest element of the tail of the list: that’s 1. It then compares 3 to 1 and picks 1 as the smallest element.

How does it find the smallest element of the tail? When it gets to 4, it recursively finds the smallest element of the tail of the list… You see where this is going. Each suffix of the list is a smaller instance of the same problem. That’s an indication that recursion is a good way to structure a solution.

So am I understanding correct that the recursion goes like this?
Smallest(3, Smallest(4, Smallest(2, Smallest(1))))
And then it compares like the following:
2 vs 1 = 1
4 vs 1 = 1
3 vs 1 = 1

The #trace operation in the top level show the inputs and results for each call to a function. (I’ve also added a type annotation to small, so that OCaml knows how to print out the list elements):

# let rec small (l1 : int list) =
match l1 with
h::[] -> h
| (h::t) -> let smallest = small t in
if h < smallest then h else smallest;;
val small : int list -> int = <fun>
# #trace small;;
small is now traced.
# small [3;4;2;1];;
small <-- [3; 4; 2; 1]
small <-- [4; 2; 1]
small <-- [2; 1]
small <-- [1]
small --> 1
small --> 1
small --> 1
small --> 1
- : int = 1

I read this as:
Q: “What is the smallest number in a list with only one number?”
A: “That number”

The second case:

| (h :: t) ->
let smallest_in_t = small t in
if h < smallest_in_t then
h
else
smallest_in_t

I read this as:
Q: “What is the smallest number in a list with many elements?”
A: "Find the smallest number in the tail, t, and compare it to the head, h".

For example, this does not work (l1 : int list ,l2 : int list) it needs to be written in a different way?

Some extra parentheses will do the job: ((l1 : int list), (l2 : int list)).

But it’s more common in OCaml not to pair up the parameters like that. The usual way of writing a multi-argument function is to separate the parameters by spaces, like this:

let rec f (l1 : int list) (l2 : int list) = ...

and then to separate the arguments by spaces when you call the function, like this: