Version française
Home     About     Download     Resources     Contact us    
Browse thread
Why Not Tail-Recursive?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: hubert.fauque@w...
Subject: Re: Why Not Tail-Recursive?

your function deepen is not tail recursive because
the recursive call to itself is enclosed in a try..with
and the function could return by its last line
        with Done -> ()
in fact it can't return by that line if there is a recursive
call to deepen because the Done would have been catched by the
recursive deepen and the function could be considered to be
tail recursive, but the compiler doesn't know that.

a possible solution is to catch the Done in
find_subsets_of_total_weight so deepen becomes tail recursive
and there is no more a stack overflow:


let find_subsets_of_total_weight all_elts wgt_fn print_fn desired_wgt =
  let elts_sorted_by_wgt = sort_elts_by_wgt all_elts wgt_fn in
  let rec next_path ( elts_so_far, wgt_so_far, undecided_elts ) =
    match elts_so_far with
    | [] -> raise Done (* no paths left *)
    | ( elt, true ) :: other_elts ->
        let new_wgt = wgt_so_far -. wgt_fn elt in
        ( ( elt, false ) :: other_elts, new_wgt, undecided_elts )
    | ( elt, false ) :: other_elts ->
        next_path ( other_elts, wgt_so_far, elt :: undecided_elts )
  in
  let rec deepen ( elts_so_far, wgt_so_far, undecided_elts ) =
      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
  in
  try (
    deepen ( [], 0., elts_sorted_by_wgt )
   ) with Done -> ()




additionnaly in the last function the 
        close_out cout
should be outside the
     with Stack_overflow



Hubert Fauque