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

[Chris Uzdavinis <chris@atdesk.com>]

Richard Jones <rich@annexia.org> writes:

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

The else clause wants to build a list using the current "a" plus
whatever the recursive invocation returns.  But it can't make its
result until the recursive call completes and returns its result, so
it must hang around for the recursive call to complete.  The 2nd call
pends waiting for the 3rd, the 3rd pends waiting for the 4th, and so
on, until they start unwinding.  Called too many times and you get the
notorious overflow.

To be tail recursive, the current function must be essentially
"finished" before it invokes itself recursively.  Usually, to
implement this you have to pass all of your state to the recursive
call, such that there is nothing left to do in the current function.
When we get to the very end of the recursion, the result is
immideately available, and no unwinding is necessary.  The result is
directly returned to the original caller.

Here is how to do it for your function, which uses an internal
function to help, and passes an accumulator (result) into the next
invocation.  Each call appends to the result when the next call is
made.  The "result" starts out empty and gets filled in one piece at
at a time by the recursive calls.

  let range a b =
    let rec range_helper aa result =
      if aa > b then result
      else range_helper (aa+1) (aa :: result)
    in
      List.rev(range_helper a [])
  ;;

Notice, the tail-recursve version builds the list backwards (because
appends go to the front), so after the internal function completes, we
reverse the list to "fix" it.

-- 
Chris

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