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

[Caml-list] How to find out if a function is tail recursive?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-06-12 (15:15) From: Brian Hurt Subject: Re: [Caml-list] How to find out if a function is tail recursive?
```On Thu, 12 Jun 2003, Richard Jones wrote:

> I was writing the section on tail recursion in the OCaml tutorial, and
> was surprised to find out that the range function (below) isn't tail
> recursive. Or at least it causes a stack overflow on a
> large-but-not-unreasonable input value.
>
> let rec range a b =
>   if a > b then []
>   else a :: range (a+1) b
>   ;;
>
> let list = range 1 1000000;;
>
> Printf.printf "length = %d\n" (List.length list);;
>
> Can you tell me why this function isn't tail recursive, and share any
> useful tips on how to tell whether a function is or is not tail
> recursive?

A function is tail recursive if it fits both of the following criteria:

1) It returns the value returned by calling itself *unmodified*.  And
modification of the return value means the functions is not tail
recursive.  This is where your example fails- it modifies the return value
br list-prepending a new item to it.  Note that even the simpliest
"modifications" defeat tail recursion.  For example, the following code is
*not* tail recursive:

let rec sum x = if x > 1 then x + (sum (x-1)) else x

Trying to calculate sum 80000 overflows the stack.  The general pattern
for how to fix this is to instead accumulate the modications into a
parameter, generally called 'accu' or 'accum' or similiar.  Often times,
the recursion is then hidden in an inner function.  So you might rewrite
the above function like:

let sum x =
let rec loop i accum =
if (i > 1) then
loop (i-1) (i + accum) (* <-- note this line! *)
else
i + accum
in
loop x 0

So now sum 80000 correctly returns 1052556352.  With lists, we can only
build lists backwards, not forwards.  So the general pattern is to build
the list backwards, then reverse it at the last moment.  So you're example
might be written like:
let range a b =
let rec loop i accum =
if i > b then accum
else loop (i + 1) (i :: accum)
in
List.rev (loop a [])

Note, we can put the list reversal either outside of the loop, or inside
of the loop just before we exit, like:

let range a b =
let rec loop i accum =
if i > b then (List.rev accum)
else loop (i + 1) (i :: accum)
in
loop a []

There's really not any difference between the two.

2) The recursive call is not within a try/with block.

So, let's consider the "classic" problem- reading all the lines of a file
into a list of strings.  The naive solution to this is:

try
let line = input_line chan in
with
End_of_file -> []

The line that reads "line :: (read_file chan)" is not tail recursive-
we're modifying our return value (by prepending the current line onto it).
This violates condition #1.  So we apply the normal pattern to it, and get
try #2:

let rec loop accum =
try
let line = input_line chan in
loop (line :: accum)
with
End_of_file -> List.rev accum
in
loop []

So now we're not modifying the return value.  Instead of prepending the
new list element to the return value, we're prepending it to the
accumulator.  So we're no longer violating condition #1.  But we're still
violating condition #2- the recursion is still within a try/with block.

The try/with block really only needs to surround the input_line call- but
it also governs wether we exit the recursion or not.  So my normal pattern
for solving this is to set a boolean variable as to wether we have data or
not.  So the code now looks like:

let rec loop accum =
let line, eof =
try
(input_line chan), false
with
End_of_file -> "", true
in
if eof then
loop (line :: accum); (* <-- note, recursion now outside *)
else
List.rev accum
in
loop []

Now the recursive call is outside the try/with block.  *And*, as we're not
modifying the return value at all, we're now tail recursive.

I'm probably missing more constraints, but it's pre-caffiene.  I'll look
at this again later.

Brian

-------------------
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

```