Re: [Caml-list] How to find out if a function is tail recursive?

[Brian Hurt <brian.hurt@qlogic.com>]

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:

let rec read_file chan =
    try
        let line = input_line chan in
        line :: (read_file chan)
    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 read_file chan =
    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 read_file chan =
    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