What is an example of a (simple) tail recursive algorithm that doesn't use a helper function?

Question

I know one can compute things using tail recursion with helper functions like:

let sum_helper n accumulator =
match n with
| 0 -> accumulator
| _ -> sum_helper (n-1) (accumulator+n-1);;

let sum_tail n = sum_helper n accumulator 0;;

sum_tail 3;;

which gives:

# sum_tail 3;;
- : int = 3

but I wanted an example of something that didn't use a helper function (idk if the above can be made without a helper function).

Ideally something simple so to understand the concept better since I'm trapped into thinking all tail recursions look like that.

Answer 1

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
  | [] -> None
  | [x] -> Some x
  | h::t -> 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
  | [] -> ()
  | h::t -> 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.

Answer 2

This is an example:

let rec all_positive l =
match l with
| [] -> true
| x::xs -> if not(x>=0) then false else all_positive xs;;

the is to notice that the function always points to return the value of the next recursive function call AND also does the main computation first. So its not accumulating anything. I don't think it can be done if an accumulator is required.