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

Explaining it like you're five

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. At no point do more than two people need to be involved in this process, while in the first scenario, the number of people involved grows linearly with the organizational depth of the office.

---

¹ "Outside the function's scope" doesn't have to mean "global" or module scope. We can hide mutable state locally. In the following, only the inner sum' function modifies the state of s, and sum' is tail-recursive.

The sum function itself does not modify any mutable state outside of its scope, and runs in constant stack space.

let sum lst =
  let s = ref 0 in
  let rec sum' = function
    | [] -> !s
    | x::xs -> s := !s + x; sum' xs
  in
  sum' lst