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: John Prevost <jmp@a...>
Subject: Re: Why Not Tail-Recursive?
>>>>> "rd" == Ruchira Datta <datta@math.berkeley.edu> writes:

    rd> I am interested in the following problem: given a set of
    rd> elements with weights, enumerate all subsets with a given
    rd> total weight.  I wrote the function
    rd> find_subsets_of_total_weight to do this in OCaml.  It works
    rd> exactly as I expect on small inputs.  But on larger (not
    rd> extremely large) inputs, I get a stack overflow.

    rd> The function deepen within find_subsets_of_total_weight
    rd> originally had an accumulating parameter subsets, but I took
    rd> that out in favor of printing out each subset as it was found,
    rd> in case that was what was causing the stack to overflow.
    rd> Unfortunately it wasn't.  I have inserted and deleted print
    rd> statements at numerous places, and in every case the function
    rd> is doing as I expect right up until the stack overflows, or at
    rd> least so it seems to me.

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

    rd> I have appended here the file weights.ml, which includes test
    rd> data leading to a stack overflow on my OCaml system.  (Bonus
    rd> points if you can guess where the test data came from.)  Any
    rd> help anyone can give me with this problem would be greatly
    rd> appreciated.  Thanks in advance.

------------------------------weights.ml------------------------------
  ...
  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 )
------------------------------------------------------------------------

Your problem is marked with >>> above.  try ... match ... around the
tail recursive call makes your call not be tail recursive.  Try
wrapping the use of deepen instead:

  in try deepen ( [], 0., elts_sorted_by_wgt) with Done -> ()

John.