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

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

```