在OOP中跟踪递归调用

我对使用Javascript，Haskell等函数式语言的递归调用进行跟踪/理解有点舒服，最近我在Scala中学习课程，目前该课程主要依靠递归。在OOP中跟踪递归调用

下面是简单的例子：

abstract class IntSet { 
    def incl(x: Int): IntSet 
    def contains(x: Int): Boolean 
    def union(other: IntSet): IntSet 
} 

class Empty extends IntSet { 
    def contains(x: Int): Boolean = false 
    def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty) 
    def union(other: IntSet): IntSet = other 
} 

class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet { 
    def contains(x: Int): Boolean = 
    if (x < elem) left contains x 
    else if (x > elem) right contains x 
    else true 

    def incl(x: Int): IntSet = 
    if (x < elem) new NonEmpty(elem, left incl x, right) 
    else if (x > elem) new NonEmpty(elem, left, right incl x) 
    else this 

    def union(other: IntSet): IntSet = 
    ((left union right) union other)incl(elem) 
}

虽然直观递归似乎可以理解的，但我有困难时期扩大一般情况下，而base case感觉完全正常。

((left union right) union other)incl(elem)

主要是因为在正常的功能语言中没有的左参考上下文。如何让自己在使用这些递归调用的同时感到舒适？

更新

基础上，我认为下面会调用扩大递归树的序列中的答案。

incl(union(union(left, right), other), elem)
incl(union(incl(union(union(left, right), other), elem), other), elem)

但我认为它会成为毛发过多很快，没有任何图案的替代或模式来理解呢？

来源

2016-08-21 CodeYogi

你是什么意思“*由于左参考上下文不存在于正常的函数式语言中*”？什么是“正常”功能语言，功能如何看待？ – Bergi

@Bergi我的意思是通常我做'函数foo（largerInstance） - >函数foo（smallerInstance）.... function foo（baseCase）'即我的函数调用仅取决于参数，但在这里我看到函数依赖于对象哪个函数被调用。 – CodeYogi

考虑一个函数被作为隐含参数调用的对象，它总是存在的（虽然并不总是使用，特别是在Scala中）。像'incl（联盟（联盟（左，右），其他），elem）'。只有所有函数的第一个参数是多态的。 –

联盟是一个棘手的方法来理解这里，这是真的。当我第一次看到它时，它看起来很有效，看起来好像很少。它有助于绘制出两棵小树，并通过它查看整个事物是如何工作的，但基本上，它与任何其他递归没有区别。大部分工作是由incl完成的，它实际上是每次将一个元素添加到int集合中。所有的union都会递归地分解这个问题，直到你得到一个空的int集合。然后逐个incl方法将每个元素都加回到集合中，将它构建到包含原始int集合中的所有元素和另一个int集合的集合中。

Odersky的课程很棒。几个月前自己完成了。

来源

2016-08-22 01:39:13 John

在OOP中跟踪递归调用

回答

相关问题