scala - Insufficient Memory behind a finite recursion -

i doing objsets coursera assignments. , faced memory problem

there insufficient memory java runtime environment continue. native memory allocation (malloc) failed allocate 253231104 bytes committing reserved memory.

when implementing union function that

def union(that: tweetset): tweetset = (left union(right)) union(that) incl(elem) 

i fixed problem changing union method to

def union(that: tweetset): tweetset = right union(left union(that)) incl(elem) 

what difference ? why iam getting memory problem in first case ? thank !

i have taken coursera course on fp scala , had same problem you. came same working solution. key knowing why 1 works , other doesn't in recursive decomposition of function. first, let's @ first solution not terminate.

def union(that: tweetset): tweetset = (left union(right)) union(that) incl(elem) 

let's use simple example tree , arbitrary tree that:

val tree = nonempty(tweet1, nonempty(tweet2, empty, empty), nonempty(tweet3, empty, empty)) val that: tweetset = ...  tree.union(that) 

expands to:

tree.left.union(tree.right)).union(that).incl(tree.elem) 

expands further to:

tree.left.left.union(tree.left.right).union(tree.right).incl(tree.left.elem).union(that).incl(tree.elem) 

now can invoke base case on empty tweetsets (tree.left.left , tree.left.right)

tree.right.incl(tree.left.elem).union(that).incl(tree.elem) 

that's far enough now, let's @ second solution.

def union(that: tweetset): tweetset = left union(right union(that)) incl(elem)   tree.union(that) 

expands to:

tree.left.union(tree.right.union(that)).incl(tree.elem) 

expand again:

tree.left.union(tree.right.left.union(tree.right.right.union(that)).incl(tree.right.elem)).incl(tree.elem) 

apply base case tree.right.left , tree.right.right

tree.left.union(that.incl(tree.right.elem)).incl(tree.elem) 

after same number of steps on each can see have different expressions.

solution1 = tree.right.incl(tree.left.elem).union(that).incl(tree.elem)

solution2 = tree.left.union(that.incl(tree.right.elem)).incl(tree.elem)

in solution 1, can see incl call occurs on left side of next union:

tree.right.incl(tree.left.elem).union(that).incl(tree.elem)            ^^^^ 

while in solution 2, incl occurs on right side of next union.

tree.left.union(that.incl(tree.right.elem)).incl(tree.elem)                      ^^^^ 

so can see solution 1 builds brand new tree before union 1 less element previous iteration. process repeat every left branch in tree processed. n^2 efficiency. memory allocation error occurs creating n^2 new trees. solution 2 uses existing tree left side of next union , returns new tree base case (efficiency of n). have efficient union given base case, must build right side of union expression because building left side result in exponentially more work.