Tail recursion

I’ve been playing around with OCaml lately and wanted to understand how tail recursion works. According to Wikipedia:

“In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion.”

Non-Tail Recursive Sum Function in OCaml

Here’s a non-tail recursive sum function in OCaml:

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

Let’s call sum [1; 2; 3] and see how it works.

1. First call: sum [1; 2; 3]

   • lst = [1; 2; 3]
   • x = 1
   • xs = [2; 3]
   • Computes 1 + sum [2; 3]

2. Second call: sum [2; 3]

   • lst = [2; 3]
   • x = 2
   • xs = [3]
   • Computes 2 + sum [3]

3. Third call: sum [3]

   • lst = [3]
   • x = 3
   • xs = []
   • Computes 3 + sum []

4. Fourth call: sum []

   • lst = []
   • Returns 0

Now, the stack unwinds:

• sum [] returns 0
• sum [3] computes 3 + 0 and returns 3
• sum [2; 3] computes 2 + 3 and returns 5
• sum [1; 2; 3] computes 1 + 5 and returns 6

In a non-tail call recursive function, each call must wait for the next call to complete and return its result.

Real-World Analogy

Imagine I work in an office and my boss asks me to find out when his lunch will be ready.

Scenario 1: I ask my secretary, who then asks the cafe manager, who then asks the chef. Each person reports back up the chain until I can tell the boss.

Scenario 2: I ask my secretary to tell the boss directly. The secretary asks the cafe manager to do the same, and the cafe manager tells the chef to inform the boss directly. The chef then tells the boss when lunch is ready.

In the second scenario, the information is passed directly to the boss at each stage, making the process more efficient. Each person only needs to relay the information once and can then move on.

Tail recursion is similar to scenario 2. Instead of waiting for each step to return its result back up the chain, each step directly passes the result to the final recipient. This makes the process more efficient and frees up resources immediately.

Credit for this analogy: https://stackoverflow.com/a/71118202

Tail Recursive Sum Function

Here’s the tail-recursive sum function in OCaml:

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

The difference here is the acc (accumulator) variable that stores the result of each recursive call. By passing the accumulated result (acc) directly in each call, tail recursion ensures that there are no deferred operations left to perform after the final call, making it much more efficient for large lists.

Let’s call tail_sum [1; 2; 3] and see how it works.

1. First call: helper 0 [1; 2; 3]

   • acc = 0
   • lst = [1; 2; 3]
   • x = 1
   • xs = [2; 3]
   • Computes helper (0 + 1) [2; 3] -> helper 1 [2; 3]

2. Second call: helper 1 [2; 3]

   • acc = 1
   • lst = [2; 3]
   • x = 2
   • xs = [3]
   • Computes helper (1 + 2) [3] -> helper 3 [3]

3. Third call: helper 3 [3]

   • acc = 3
   • lst = [3]
   • x = 3
   • xs = []
   • Computes helper (3 + 3) [] -> helper 6 []

4. Fourth call: helper 6 []

   • acc = 6
   • lst = []
   • Returns 6

Stack Visualization for Tail Recursive Sum

• First call: helper 0 [1; 2; 3]
  • Second call: helper 1 [2; 3]
    • Third call: helper 3 [3]
      • Fourth call: helper 6 []
      • Returns 6

Each call computes the result and immediately passes it to the next call, without building up a stack of deferred operations. The final call returns the accumulated result directly. It’s just like in scenario 2 in the lunch example, where each step directly informs the boss, leading to better performance and resource efficiency.

Summary

Non-tail recursive functions suffer from the following problems:

• Memory Usage: Each recursive call adds a new frame to the call stack. This can lead to high memory usage, and in cases of deep recursion, can cause a stack overflow.
• Time Consumption: Each call must wait for all subsequent calls to complete, leading to longer overall execution times.
• Resource Allocation: The resources (like CPU and memory) are tied up until all calls are resolved, which can be wasteful and impact performance.

In contrast, a tail-recursive function is more efficient. In a tail-recursive function, the final result of each recursive call is immediately returned to the previous call, allowing the current call to be completed and its stack frame to be freed. This process continues until the base case is reached, ensuring that only a single stack frame is used regardless of the depth of the recursion.