This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] beginner question about tail recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Matt Gushee Subject: Re: [Caml-list] beginner question about tail recursion
```On Sat, Aug 30, 2003 at 03:52:04PM -0700, Ram Bhamidipaty wrote:
> Hi I am just getting started with OCaml. My understanding is
> that it is desirable to write function in a tail recursive style.

Well, I'm just getting started with *explaining* OCaml, so don't be
surprised if I get it wrong. But here's how I understand it:

> Can the OCaml system tell me if a function is tail recursive?

I don't think so. But it's pretty easy to tell by inspecting the code,
once you get used to it.

There are two basic rules you need to keep in mind:

1. The recursive call must be the very last thing that happens in the
function. Another way of saying this is that the function must
directly return the result of the recursive call to itself, with
absolutely no modification.

2. The recursive call can't be within a 'try' block.

Unfortunately, this means that the most intuitive pattern for many
functions (which is also the pattern found in many introductory
examples) is not tail recursive.

[ The following is mostly stolen from a previous post by Brian Hurt
--thanks, Brian ]
A common example of the problem is a function that reads from an input
channel and returns all the lines as a list. The most obvious way to
write this function is:

1  let rec readlines chnl =
2    try
3      let line = input_line chnl in
5    with End_of_file -> []

This actually breaks both of the two rules. Rule #1 is broken in line 4,
because the cons operation ('::') is applied to the result of the
recursive call. And of course it is within a 'try' block.

A tail-recursive way to write the function would be:

let rec readlines chnl lines =
let line, eof =
try
let ln = input_line chnl in
ln, false
with End_of_file ->
[], true in
if eof then lines            (* result returned unmodified *)
else readlines chnl (line :: lines)
(* 'line :: lines' is evaluated before

Note the use of an accumulator (the 'lines' parameter). This is
something you often need for a tail-recursive function.

** Note to OCaml documentors **
Isn't it confusing to beginners that non-tail-recursive examples are so
common in introductory documentation? I would suggest adding warnings
along the lines of

"The above example illustrates the simplest way to write a recursive
function; this is not the most efficient form, and should be avoided
of tail recursion in Chapter XX."

--
Matt Gushee                 When a nation follows the Way,
Englewood, Colorado, USA    Horses bear manure through
mgushee@havenrock.com           its fields;
http://www.havenrock.com/   When a nation ignores the Way,
Horses bear soldiers through
its streets.

--Lao Tzu (Peter Merel, trans.)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

```