Golangにおけるバイナリーツリー（BST) の再帰の仕方について

Question

Golangのバイナリーツリー（BST）における、再帰（Recursion) のやり方について疑問があり質問させていただきます。例えば以下のようなバイナリーツリーが構成されており、こちらを再帰を利用することで最小値~最大値を順番とするスライスを生成するとします。
（この場合であれば：[1, 2, 5, 5, 10, 15, 22]が正解）

        10            
       /    \
      5      15
     / \       \
    2   5       22
   /
  1
   

コードとしては、以下のように記述することで求めるアウトプットを出せるのですが、なぜこちらのコードが成り立つのかが良く理解できていません。
例えば、まず if tree.Left != nilを通してnodeを1まで進め（リーフノード）、そのループ時はnilとなるのでappendされる点までは分かりました。ただ、その後、if tree.Right !=nilに進むと思うのですが、この時点で treeは1上にあるため、tree.Right == nilを返してしまい、関数が終了してしまうのではという理解をしています。

疑問点の仮説をまとめさせていただきました。

• 1のリーフノードに届くまで3回再帰しています。例えば初回の再帰が呼ばれると、ノード自体は5に移動すると思いますが、この時点では tree.Left != nil のif文に入るため、appendまでは行かず、一度ここで止まり（？）処理待ちの状態となる
• そして, 1に到達すると、if文には入らないため、append, 次のif分を処理し、一度return（？）する
• その後、処理が止まっていた再帰の処理が新しい順から始まる

おそらくこちらの流れなのだと思うのですが、再帰をする際にif文にはまると処理待ちの状態になるのか・１に到達してreturnすると処理待ちがなぜ再開するのかが、あまりスッキリしていません。加えて、現状の理解で間違っている点がありましたらご指摘いただけると幸いです。よろしくお願い致します。

type BST struct {
    Value int

    Left  *BST
    Right *BST
}

func (tree *BST) InOrderTraverse(array []int) []int {
    if tree.Left != nil {
        array = tree.Left.InOrderTraverse(array)
    }   

    array = append(array, tree.Value)
    if tree.Right != nil {
        array = tree.Right.InOrderTraverse(array)
    }
    return array
}

Comments

[hoshi-takanori]

ループじゃなくて再帰ですね。

[huskies]

ご指摘ありがとうございます。修正いたします

[hoshi-takanori]

「この時点で treeは`1`上にあるため、`tree.Right == nil`を返してしまい、関数が終了してしまうのではという理解をしています。」の部分ですが、関数が 1 回終了するのは確かですが、それまでに何回呼ばれたかを考えましょう。

[huskies]

ありがとうございます。投稿を修正し、疑問点をまとめさせて頂きました。具体的には、なぜ処理が一度止まるのか、関数が一度終了したのち、それまでに呼ばれた処理待ちが動き出すフローが何となく分かるのですが、まだ曖昧でご説明いただければ幸いです。

Answer 1

1つずつ回答します。

huskiesさんの理解について

例えば、まずif tree.Left != nilを通してnodeを1まで進め（リーフノード）、そのループ時はnilとなるのでappendされる

不明瞭なので、書き直すと下記の通りです。

if tree.Left != nilを通して、10, 5, 2のノードにおいてtree.Left.InOrderTraverse(array)が呼び出され、最終的に1のノードでtree.Leftがnilになるので、array = append(array, tree.Value)が実行される。ここで重要なのは、10, 5, 2のノードでの呼び出しはリターンされず、スタックに積まれたままである(実行中)ということです。そのため、1のノードの実行が終了してもその後2のノードが引き続き実行されます。

したがって、その後の記述で、

関数が終了してしまうのでは

と書かれていますが、1のノードに生えているメソッドInOrderTraverseについて、この理解は正しいです。
(本質ではないですが、InOrderTraverseはレシーバに生えているので関数ではなくメソッドです。)

huskiesさんの仮説について

1のリーフノードに届くまで3回再帰しています。例えば初回の再帰が呼ばれると、ノード自体は5に移動すると思いますが、この時点では tree.Left != nil のif文に入るため、appendまでは行かず、一度ここで止まり（？）処理待ちの状態となる

正しいです。

そして, 1に到達すると、if文には入らないため、append, 次のif分を処理し、一度return（？）する

正しいです。

その後、処理が止まっていた再帰の処理が新しい順から始まる

「新しい順から始まる」という言葉を明確にすると、「2のノードのarray = tree.Left.InOrderTraverse(array)の代入が実行される」です。

huskiesさんの質問について

下記の加算結果を代入するコードが実行される時を考えます。

func main() {
  sum := 1 + 2
  fmt.Println(sum)
}

詳細に書くと長くなるので、概要だけ掻い摘むと

1. 1 + 2が評価される
2. 1 + 2の評価した結果をsumに代入する

という2つの過程に分けられます。
ここで、1 + 2の評価が終わるまで代入が為されないことが分かると思います。

次に、下記の関数呼び出し結果を代入するコードが実行される時を考えます。

func One() int {
  return 1
}

func main() {
  result := One()
  fmt.Println(result)
}

この場合も同様に、

1. One()が評価される
2. One()を評価した結果をresultに代入する

という2つの過程に分けられます。
ここで、One()の評価が終わるまで代入が為されないことが分かります。

これをInOrderTraverse(array)に置き換えて考えてください。
もう説明は要らないでしょう。

補足

実際に実行される順番を見るために、Playgroundのコードを開いて、Runして得られた結果を見てください。すると、呼び出される順番が分かります。

このように、実行順序を知るために各行で結果を出力するのは良く使う手法です。他には、gdbなどのデバッガで処理手順を知るのも1つの手段だと思います。詳しくはググってください。

一応ソースコードと結果を載せておきます。

package main

import "fmt"

type BSTNode struct {
	Value int

	Left  *BSTNode
	Right *BSTNode
}

func (tree *BSTNode) Traverse(array []int) []int {
	fmt.Printf("[Called     ] array: %v, now: %d\n", array, tree.Value)
	// 左のノードがあれば、そちらのノードで更にトラバースする
	if tree.Left != nil {
		fmt.Printf("[CallLeft   ] array: %v, now: %d\n", array, tree.Value)
		array = tree.Left.Traverse(array)
		fmt.Printf("[CalledLeft ] array: %v, now: %d\n", array, tree.Value)
	}

	// arrayに今見ているノードの値を追加する
	array = append(array, tree.Value)
	// 右にノードがあれば、そちらのノードで更にトラバースする
	if tree.Right != nil {
		fmt.Printf("[CallRight  ] array: %v, now: %d\n", array, tree.Value)
		array = tree.Right.Traverse(array)
		fmt.Printf("[CalledRight] array: %v, now: %d\n", array, tree.Value)
	}
	fmt.Printf("[Return     ] array: %v, now: %d\n", array, tree.Value)
	// トラバースした結果を返す
	return array
}

// ※バックスラッシュが出せなかったので、\で代用しています
//         10
//       /    \
//      5      15
//     / \       \
//    2   6       22
//   /
//  1

func main() {
	// ノードを作る
	node1 := &BSTNode{Value: 1, Left: nil, Right: nil}
	node2 := &BSTNode{Value: 2, Left: node1, Right: nil} // node1というノードを左の子として保持している(以下略)
	node6 := &BSTNode{Value: 6, Left: nil, Right: nil}
	node5 := &BSTNode{Value: 5, Left: node2, Right: node6}
	node22 := &BSTNode{Value: 22, Left: nil, Right: nil}
	node15 := &BSTNode{Value: 15, Left: nil, Right: node22}
	node10 := &BSTNode{Value: 10, Left: node5, Right: node15}

	// 根からトラバースし始める
	fmt.Println(node10.Traverse([]int{}))

	// BITの格納順序が壊れていた場合は、最小値～最大値に出力されない
	// この場合は5と6を反転させている
	node5 = &BSTNode{Value: 5, Left: nil, Right: nil}
	node6 = &BSTNode{Value: 6, Left: node2, Right: node5}
	node10 = &BSTNode{Value: 10, Left: node6, Right: node15}
	// 根からトラバースし始める
	fmt.Println(node10.Traverse([]int{}))

}


// Output:
// [Called     ] array: [], now: 10
// [CallLeft   ] array: [], now: 10
// [Called     ] array: [], now: 5
// [CallLeft   ] array: [], now: 5
// [Called     ] array: [], now: 2
// [CallLeft   ] array: [], now: 2
// [Called     ] array: [], now: 1
// [Return     ] array: [1], now: 1
// [CalledLeft ] array: [1], now: 2
// [Return     ] array: [1 2], now: 2
// [CalledLeft ] array: [1 2], now: 5
// [CallRight  ] array: [1 2 5], now: 5
// [Called     ] array: [1 2 5], now: 6
// [Return     ] array: [1 2 5 6], now: 6
// [CalledRight] array: [1 2 5 6], now: 5
// [Return     ] array: [1 2 5 6], now: 5
// [CalledLeft ] array: [1 2 5 6], now: 10
// [CallRight  ] array: [1 2 5 6 10], now: 10
// [Called     ] array: [1 2 5 6 10], now: 15
// [CallRight  ] array: [1 2 5 6 10 15], now: 15
// [Called     ] array: [1 2 5 6 10 15], now: 22
// [Return     ] array: [1 2 5 6 10 15 22], now: 22
// [CalledRight] array: [1 2 5 6 10 15 22], now: 15
// [Return     ] array: [1 2 5 6 10 15 22], now: 15
// [CalledRight] array: [1 2 5 6 10 15 22], now: 10
// [Return     ] array: [1 2 5 6 10 15 22], now: 10
[1 2 5 6 10 15 22]
// [Called     ] array: [], now: 10
// [CallLeft   ] array: [], now: 10
// [Called     ] array: [], now: 6
// [CallLeft   ] array: [], now: 6
// [Called     ] array: [], now: 2
// [CallLeft   ] array: [], now: 2
// [Called     ] array: [], now: 1
// [Return     ] array: [1], now: 1
// [CalledLeft ] array: [1], now: 2
// [Return     ] array: [1 2], now: 2
// [CalledLeft ] array: [1 2], now: 6
// [CallRight  ] array: [1 2 6], now: 6
// [Called     ] array: [1 2 6], now: 5
// [Return     ] array: [1 2 6 5], now: 5
// [CalledRight] array: [1 2 6 5], now: 6
// [Return     ] array: [1 2 6 5], now: 6
// [CalledLeft ] array: [1 2 6 5], now: 10
// [CallRight  ] array: [1 2 6 5 10], now: 10
// [Called     ] array: [1 2 6 5 10], now: 15
// [CallRight  ] array: [1 2 6 5 10 15], now: 15
// [Called     ] array: [1 2 6 5 10 15], now: 22
// [Return     ] array: [1 2 6 5 10 15 22], now: 22
// [CalledRight] array: [1 2 6 5 10 15 22], now: 15
// [Return     ] array: [1 2 6 5 10 15 22], now: 15
// [CalledRight] array: [1 2 6 5 10 15 22], now: 10
// [Return     ] array: [1 2 6 5 10 15 22], now: 10
// [1 2 6 5 10 15 22]

要点だけを話したので、更に詳しく知りたい場合は「関数 呼び出し 仕組み」や「再帰 スタックメモリ」などで調べると良いと思います。ここら辺はコンピュータサイエンスの分野になるので、「実行できれば良い」というスタンスなら別に知る必要はないと思います。

長くなりましたが、プログラムが実行される時にどのように実行されるかを理解するのは非常に重要で為になります。引き続き頑張ってください。