OOPで再帰呼び出しをトレースする

Question

Javascript、Haskellなどの関数型言語で再帰呼び出しをトレース/理解するのはやや快適ですが、最近私はScalaでコースを取っていますが、現在コースは再帰に大いに依存しています。直感的に再帰が理解できるようだが、私はbase caseは完全に罰金感じているのに対し、一般的なケースを広げ苦労しておりますが

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) 
} 

：ここ

は簡単な例です。

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

通常、通常の機能的言語には存在しない左参照コンテキストのためです。これらの再帰呼び出しで作業して理解しながら、自分を快適にする方法を教えてください。

私は再帰ツリーを展開する一連のコールだろう以下だと思う回答に基づいて更新

。

1. incl(union(union(left, right), other), elem)
2. incl(union(incl(union(union(left, right), other), elem), other), elem)

しかし、私はそれは非常にすぐにあまりにも毛深いなると思いますが、これを理解するために任意の絵の代替またはモーダルはありますか？

Answer 1

ここで理解するのは難しい方法ですが、それは本当です。私が最初にそれを見たとき、それはまったく機能しないように見えました。 2つの小さな木を引っ張って全体の仕組みを調べるのに役立ちますが、本質的には他のどの再帰とも変わりません。ほとんどの作業はinclによって行われます。これは、実際にはすべての要素を一度に1つずつintセットに追加しています。あなたが空のint型になるまで、すべてのunionは再帰的に問題を繰り返し解きます。次に、1つずつのinclメソッドは、すべての要素をセットに戻し、元のintセットとそれ以外のintセットのすべての要素を含むセットまで構築します。

途方もないオーデスキーのコースです。数ヶ月前にそれを完成させました。