Back to Questions
834
views2
comments
Cursed Recursion - Stack overflow
f#

Hi all,

I have a recursive function that looks for the intersection between two sorted lists, it looks something like: 

1
2
3
4
5
6
7
8

#light 

let rec AinB listA listB =
  if       listA = [] then []
  else if  listB = [] then []
  else if  listA.Head < listB.Head then AinB listA.Tail listB 
  else if  listA.Head > listB.Head then AinB listA listB.Tail
  else    listA.Head :: AinB listA.tail listB

Now everything seems to be happy when I am writing this on small data sets (5 - 10 list entries), but when I scale up to large data sets (40,000+ entires) I get stack overflows.

My questions is, can anyone suggest an elegant way around this problem?

Any help would be fantastic!
Matt

.

Hi Matt,

Why not just use the Set module to compute the intersection?

1
2
3
4
5
6

#light 
let set1 = Set.of_list [ 1 .. 40000 ]
let set2 = Set.of_list [ 20000 .. 60000 ]
let intersect = Set.inter set1 set2
let intersect_list = Set.to_list intersect
print_any intersect_list

The other option would be to refactor your code to ensure your function is tail recusive (ie the recursive call must always be the last call you make), tail recusive function never stack over flow. However this can be a little tricky.

Cheers,
Rob

By on 8/10/2007 7:13 AM ()

Hi Rob,

Thanks for your quick response (as always). You need hardly guess, but actually the problem is a little more complex than I presented. The code presented is an oversimplification that hides some of the ugliness of my ADT away. One of the reasons for using lists over sets as a base type is that there is likely to be double entires involved and I have a consistent way of working with them that the set intersection does not. Pitty though.

Anyway, thanks for your suggestion to refactor my code to be tail recursive. A quick Google and some fast coding solved the problem. For anyone interested, the important thing I found was a quote from IBM on XSL programming: "The basic idea behind Tail Recursion is to eliminate the storage of any state information across the recursive steps. All information that would ever be needed at any single step is passed as a parameter to the function instead of being stored at some higher level in the recursion stack." IMHO this is actually quite straightforward to do, it just requires introducing a "state parameter" into the function and seeding it:

1
2
3
4

#light 

let AinB listA listB  =
  RecAinB listA listB []
1
2
3
4
5
6

let rec RecAinB listA listB retList =
  if       listA = [] then retList
  else if  listB = [] then retList
  else if  listA.Head < listB.Head then AinB listA.Tail listB retList
  else if  listA.Head > listB.Head then AinB listA listB.Tail retList
  else    AinB listA.tail listB (listA.Head :: retList)

Again this is an oversimplification of what my code is doing, but the principal is the same.

Thanks again!
Matt

By on 8/10/2007 7:54 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper