What is an example of a (simple) tail recursive algorithm that doesn't use a helper function?
There's an example staring at you in the face: write a function that takes two arguments a and b and returns the sum of the integers from 0 to a, plus b.

Here's another example: write a function that returns the last element of a list, or a special value if the list is empty.

let rec last l =
  match l with
  | [] -&gt; None
  | [x] -&gt; Some x
  | h::t -&gt; last t


Here's another example, in an imperative language: apply a function to all the elements of a list, in order, without returning a value.

let rec iter f l =
  match l with
  | [] -&gt; ()
  | h::t -&gt; f h; iter f t


So you can see that tail-recursive don't have to take an extra argument. However, taking an extra argument is a common pattern, and there is a deep reason for that.

A common reason to write a recursive function is to traverse a recursive data structure. For example, the list data structure is defined recursively: a list is either the empty list (“nil”), or a pair (“cons”) consisting of an element (“head”) and a list (“tail”). In Ocaml syntax:

type list_of_foo = Foo_nil | Foo_cons foo * list_of_foo;; (* Foo_cons (head, tail) *)


To act on a list, you need to specify what to do on the empty list, and what to do on a non-empty list. To traverse the whole list with a function, you make a recursive call to process the tail in the case of a non-empty list. A generic list traversal is called a fold. Writing a recursive function is one way to write a fold; another way is to call a generic fold function and tell it what to do with nil and what to do with a cons (as a function of the head and the result of processing the tail of the list).

This generalizes to all recursive data structures. A particularity of lists is that there's never more than one sub-list, so the call to process the tail can be a tail call. Contrast with a binary tree, for example:

type btree = Leaf of int | Node of btree * btree


To process a btree, when you reach a Node, you need to process both the first subtree (left child) and the second subtree (right child). They can't both be tail calls. But with lists, the one recursive call can be a tail call.

Integers don't look much like a data structure. But in fact recursion on an integer is typically based on the structure of integers. For example, when you recurse by enumerating integers from 0 to n or from n to 0 (or 1 to n, etc.), you're using the structure provided by the Peano axioms: an integer is either 0 or the successor of an integer.

So you have a recursive function which takes a data structure as an argument. It makes a recursive call, calling itself on a sub-structure of the original data. What does it return? If the recursive call is a tail call, what it returns has to be the value returned in a case where the function doesn't make a recursive call. Often, that's the “starting” case, e.g. 0 for a function that recurses on an integer or the empty list for a function that recurses on a list. What can you return in the starting case? If you return a constant, that's not very interesting. If you want to return something that depends on information collected from the data structure, you need to pass this information through the tail calls. And that's where the extra argument comes from. A tail-recursive function needs an extra argument (in addition to the data structure that it recurses over) to collect data read from the data structure.

In the starting case, you often do want to return a constant. Hence you write a pair of functions: a tail-recursive functions with two arguments (the data structure to traverse and the accumulator), which returns the accumulator when it reaches the end of the data; and an auxiliary function just to give an initial value to the accumulator. This corresponds to the initial value argument for fold functions.