Re: Why Not Tail-Recursive?

[Alain Frisch <frisch@clipper.ens.fr>]

On Wed, 25 Oct 2000, Ruchira Datta wrote:

> The only thing I can think of is that the functions deepen and next_path
> are not actually tail-recursive as I expected them to be.  But why not?  

deepen is not tail recursive: the recursive call is followed by the
the exception handler (which must be desinstalled, even if it doesn't
catch any exception).

For instance:
let f x =
    try f x with Not_found -> ();;

will raise a Stack overflow when executed.

If you want the exception to stop the computation, install the handler
around the toplevel call of deepen.


>   let rec deepen ( elts_so_far, wgt_so_far, undecided_elts ) =
>     try (
>       match undecided_elts with
>       | [] -> 
>         let new_path = next_path ( elts_so_far, wgt_so_far, undecided_elts ) 
>         in deepen new_path
>       | elt :: elts ->
>         let new_wgt = wgt_so_far +. wgt_fn elt in
>         if new_wgt < desired_wgt then
>           deepen ( ( ( elt, true ) :: elts_so_far ), new_wgt, elts )
>         else if new_wgt = desired_wgt then
>           let _ = print_fn ( ( elt, true ) :: elts_so_far ) in
>           deepen ( ( ( elt, false ) :: elts_so_far ), wgt_so_far, elts )
>         else (* new_wgt > desired_wgt *)
>           let new_path = next_path ( elts_so_far, wgt_so_far, undecided_elts ) 
>           in deepen new_path
>     ) with Done -> ()
>   in deepen ( [], 0., elts_sorted_by_wgt )


-- 
  Alain Frisch