Can someone explain OCaml Tail Recursion Like I am five?

I cant wrap my brain around tail recursion specifically in ocaml also explain why one calls the "in" function at the end. P.S. I am talking most basic tail recursive function.

Solution

A tail call is the last expression in a function, which becomes the result of the whole function, e.g.,

let foo x = x + 1
let bar x = 
  let x = x + 1 in
  foo x (* here foo is in the tail position *)

When a call is in the tail position, it could be made very cheaply, without allocating any administrative data on the program stack, which is usually necessary for more general calls, e.g.,

let baz x = 
  1 + foo x (* foo is not in the tail position! *)

In this example, we see that <...> + <...> is the last expression, so the computer needs to evaluate both sides of + and store them in some place in the memory before it can finally sum them up. This "some place in the memory" is usually the stack, which is a scarce resource on most modern operating systems. The scarcity of the stack becomes especially important if we make such calls iteratively.

Finally, if a tail call is recursive, it is called a tail-recursive call. Tail-recursive calls are very efficient in the implementation of iterative procedures, where instead of relying on specialized ad-hoc control-flow structures, like for and while, we can express the repetitiveness of the process in a more legible way, e.g.,

let rec contains_element k = function
  | [] -> false
  | x :: _ when k = x -> true
  | _ :: xs -> contains_element k xs

describes naturally that a list contains an element k if either its head is k or if the tail of the list contains the element k. This algorithm is also a good showcase for an exception to the above-specified rule that a tail calls must be the last call in the function,

(* this version is also tail recursive! *)
let rec contains_element k = function
  | [] -> false
  | x :: xs -> x = k || contains_elements xs

It is because OCaml treats a call on the right-hand side of a short-circuit operator¹ as a tail call, since you don't need to compute both operands before applying the operator.

¹⁾ which are || and && in OCaml that stand for logical disjunction (OR) and conjunction (AND).