Insufficient memory behind finite recursion

Question

I am doing coursera objsets jobs. And I ran into a memory problem

There is not enough memory for the Java Runtime Environment to continue. The configured memory allocation (malloc) could not allocate 253231104 bytes for memory backup.

when implementing such a union function that

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

I fixed the problem by changing the join method to

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

What is the difference? why does iam get a memory problem in the first case? Thanks!

Answer 1

I also took the FP Course with Scala and had the same problem as you. I also came up with the same solution. The key to understanding why it works and the other doesn't, is the recursive decomposition of a function. First, let's look at your first decision, which does not end there.

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

let's use a simple tree of examples and some 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) 

Further expanded:

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

Now we can call the base register on empty tweets (tree.left.left and tree.left.right)

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

Still far enough, let's look at the 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) 

Deploy again:

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

Apply the base case for tree.right.left and tree.right.right

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

After the same number of steps, each of them shows that we have very 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, you can see that the call to incl occurs on the left side of the following union :

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

and in solution 2, incl happens on the right side of the next union .

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

So, we see that solution 1 creates a new tree before merging with one smaller element than the previous iteration. This process will be repeated for each left branch of the tree to be processed. Efficiency n ^ 2. The memory allocation error arises from the creation of n ^ 2 new trees. Solution 2 uses the existing tree as the left side of the next union and returns a new tree from the base case (efficiency n). To have an effective union with this base case, you must create the right side of the union expression, because creating the left side will exponentially increase the work.