scala – 有限递归背后的内存不足

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

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

我也使用Scala参加了有关FP的Coursera课程,并遇到了和你一样的问题.我也提出了相同的工作解决方案.知道为什么一个有效而另一个无效的关键在于函数的递归分解.首先,让我们看看你的第一个没有终止的解决方案.

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

让我们使用一个简单的示例树和一些任意树：

val tree = NonEmpty(tweet1,NonEmpty(tweet2,Empty,Empty),NonEmpty(tweet3,Empty))
val that: TweetSet = ...

tree.union(that)

扩展到：

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

进一步扩展到：

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

现在我们可以在Empty TweetSets上调用基本案例(tree.left.left和tree.left.right)

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

现在已经足够了,让我们来看看第二个解决方案.

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


tree.union(that)

扩展到：

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

再次展开：

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

为tree.right.left和tree.right.right应用基础案例

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

在每个步骤相同的步骤后,您可以看到我们有非常不同的表达式.

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

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

在解决方案1中,您可以看到incl调用发生在下一个联合的左侧：

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

在解决方案2中,incl发生在下一个联合的右侧.

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

因此,我们可以看到解决方案1在联合之前构建一个全新的树,其元素比前一次迭代少一个.对于将要处理的树中的每个左分支,将重复此过程. n ^ 2效率.创建n ^ 2个新树时会发生内存分配错误.解决方案2使用现有树作为下一个联合的左侧,并从基本情况返回新树(效率为n).要与给定的基本情况保持有效的联合,您必须构建联合表达式的右侧,因为构建左侧将导致指数级更多的工作.