Coursera Scala课程二叉树集递归union函数无法终止问题咨询

核心问题是错误实现破坏了递归必须满足的问题规模持续收敛到终止条件的原则。

正确实现的递归逻辑 #

参考实现的NonEmpty.union代码：

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

它的递归调用规则是：每次作为调用主体的都是当前节点的左/右子树，子树的节点数必然小于当前树的节点数，递归深度越深，调用主体的规模越小，最终一定会走到Empty节点调用union，而Empty.union直接返回参数作为终止，不会产生无限递归。

错误实现的问题 #

你写的错误代码：

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

这里你把union的调用主体换成了参数that，而非当前节点的子树，这就导致两个问题：

• 递归过程中调用主体的规模没有必然缩小的保证，that是外部传入的另一个集合，它的大小和当前树的递归深度没有任何关联。
• 当两个非空集合合并时，会出现“来回调用”的死循环场景：比如调用A.union(B)（A、B都是NonEmpty），第一步会变成B.union(...)，B的union执行时又会变成它的参数（A的左右子树合并结果）调用union，如果这个参数也是NonEmpty，又会反过来把B的子树合并结果作为参数调用union，只要双方的子树合并结果始终有非空的情况，就永远碰不到Empty作为调用主体触发终止条件，程序自然无法终止。

内容的提问来源于stack exchange，提问作者RonB