Can someone explain OCaml Tail Recursion Like I am five?

Question

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.

Answer 1

Functions communicate via one of three methods.

1. Their argument(s). This is the input data.
2. Their return value. This is the output.
3. They can modify some mutable state outside of the function's scope. Don't do this if you can possibly avoid it.

Everytime a function is called, a stack frame is created with the data the function needs to do its job. When it's done its return value is returned "up" the stack to its caller.

Consider a simple sum function which sums up a list.

let rec sum lst =
  match lst with
  | [] -> 0
  | x::xs -> x + sum xs

Pretty simple. The sum of an empty list of course is 0. The sum of a non-empty list is the first element plus the sum of the rest of the list.

When we recursively call sum xs that call doesn't know what x is. It can't perform that addition. It can only sum the remaining list and then send that back up the stack for the addition to happen.

If we do this with a small list, it's not really an issue. The stack is limited, but not limited enough for that to be a concern.

But if we tried it with a list with a much larger number of elements, we'll run out of stack space and get an error.

The tail-recursive version of the sum function needs to make sure that its last call can provide a complete answer with no need to return info back up the stack. That means when the function is called, the caller needs to pass any required information to the called via its argument(s).

To accomplish this, we use an accumulator, which is commonly called acc.

let rec tail_sum acc lst =
  match lst with 
  | [] -> acc
  | x::xs -> tail_sum (acc + x) xs

As tail_sum iterates over the list, it keeps a running accumulation of the sum. When the list is empty, it returns that accumulator. We just need to always call tail_sum with a starting accumulator of 0.

tail_sum 0 [1; 2; 3; 4; 5; 6]

This is ugly, so you'll commonly see this hidden by using a locally nested helper function.

let tail_sum lst =
  let rec helper acc lst =
    match lst with 
    | [] -> acc
    | x::xs -> helper (acc + x) xs
  in
  helper 0 lst

---

Imagine I work in an office. My boss asks me to find out when his lunch is going to be ready.

Scenario 1: I ask my secretary to tell me when lunch will be ready. He asks the cafe manager to tell him when lunch will be ready. The cafe manager asks the chef to tell her when lunch will be ready. They all report back to each other, and eventually to me, and I tell the boss when lunch will be ready.

Scenario 2: I ask my secretary to tell the boss when lunch will be ready. My secretary tells the cafe manager to tell the boss when lunch is ready. The cafe manager tells the chef to tell the boss when lunch is ready. The chef directly contacts the boss with the requested information.

The more direct approach in scenario 2 is possible because the information about the end recipient is passed along at each stage. The same goal is achieved, but this time once it has exited each person's hands, they can forget about it. They are no longer necessary to achieving the goal.

Answer 2

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).