Why Not TailRecursive?

Ruchira Datta
 hubert.fauque@w...
 bcpierce@c...
 Alain Frisch
 John Prevost
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  John Prevost <jmp@a...> 
Subject:  Re: Why Not TailRecursive? 
>>>>> "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 tailrecursive 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.