在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中跟蹤遞歸調用

回答

相關問題