OCaml

Tail recursion

Introduction#

Functional languages such as OCaml rely heavily on recursive functions. However, such functions can lead to memory over consumption or, when handling large datasets, to stack overflows.

Tail recursion is an important source of optimization in such cases. It allows a program to drop the caller context when the recursive call is the last of the function.

Sum function

Below is a non-tail-recursive function to compute the sum of a list of integers.

let rec sum = function
  | [] -> 0
  | h::t -> h + (sum t)

The last operation the function performs is the addition. Thus, the function isn’t tail-recursive.

Below is a tail-recursive version of the same function.

let sum l =
  let rec aux acc = function
    | [] -> acc
    | h::t -> aux (acc+h) t
  in
  aux 0 l

Here, the aux function is tail-recursive: the last operation it performs is calling itself. As a consequence, the latter version of sum can be used with lists of any length.


This modified text is an extract of the original Stack Overflow Documentation created by the contributors and released under CC BY-SA 3.0 This website is not affiliated with Stack Overflow