再帰呼出しをVS Codeコールスタックで理解(Pythonで二分探索木操作例)

## はじめに

再帰呼出しのフローはややこしく、頭で追うと、頭が痛くなるものです。
本記事の目的は、再帰呼出しを可視化しわかりやすく理解することです。

## 再帰呼出し(recursive call)とは

- プログラミング技法の一つで、ある関数中で再びその関数自身を呼び出すこと
- 再帰的な構造を持つ`階乗計算`や`フィボナッチ数列`など、再帰的アルゴリズムの記述に適している

※ 引用元: https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0

## 二分木と二分探索木とは

- 二分木(binary tree)とは
    - データ構造の1つで、木構造の全てのノード(node)が最大二つの子を持つ
        - 2つの子を、それぞれ`左` `右`と呼ぶ

- 二分探索木(binary search tree)
    - `左の子孫の値 ≤ 親の値 ≤ 右の子孫の値` という制約を持つ二分木
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/10af31c7-b02f-c0c0-0e2a-bb1b8bd3f6f0.png)


※ 引用元: https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8

## 事前準備

- Python
- VS Code

## 使用する再帰呼出しの例

- 再帰を使った二分探索木操作をPythonで実装
    - 入力値でノード追加
    - 二分探索木を出力

## サンプルコード

- 各種処理の説明は、コード内コメントをご参照ください

```recursive.py
# 目的: 再帰を使って2分探索木を操作

# 2分探索木ノードのクラス
class Node:
  def __init__(self, value: int):
    self.value = value
    self.left = None
    self.right = None

# 再帰を使って2分探索木にノード追加
# 戻り値: ルートノード
def add_node(root: Node, value: int) -> None:
  # ルートがNoneだったら、ノード作成しリターン
  if root is None:
    root = Node(value)
    return root

  # 値がルートより小さい場合、ルートの左子ノードをルートとし再帰
  if value < root.value:
    root.left = add_node(root.left, value)  # 左の子をルートと指定し、再帰呼出し
  # 値がルートより大きい場合、ルートの右子ノードをルートとし再帰
  elif value > root.value:
    root.right = add_node(root.right, value)  # 右の子をルートと指定し、再帰呼出し
  # 同じ値が存在する場合、メッセージ出力し、リターン
  else:
    print('同じノードが存在します、別の値を入力してください。')

  return root

# 再帰を使って二分探索木をプリント
# 第2引数: ノードの深さ
# 第3引数: 左の子ノード: 'L', 右の子ノード: 'R'
def print_tree(node: Node, level: int, side: str) -> None:
  if node is None:
    return
  print("{} {}{}".format('*' * level, node.value, side))  # '*'の数でノードの深さを表す
  print_tree(node.left, level + 1, 'L')  # 左の子をルートと指定し(深さ+1)、再帰呼出し
  print_tree(node.right, level + 1, 'R')  # 右の子をルートと指定し(深さ+1)、再帰呼出し

if __name__ == "__main__":
  # 二分探索木の初期状態は空
  root = None

  # Enterキーを押すまで、ループしながら入力を受け付ける
  while True:
    input_val = input("number=>")
    if input_val:  # 値を入力した場合
      try:
        value = int(input_val)
      except:
        print('整数を入力してください。')
        continue
      root = add_node(root, value)  # 二分探索木にノードを追加
    else:  # Enterで空値が入力されたら、二分探索木を出力し終わり
      print_tree(root, 1, '')  # 第2引数はノードの深さ、第3引数は親ノードの左か右か
      break
```

## VS Codeでサンプルコードをデバッグ実行

- print_tree関数の先頭にブレークポイントを設置
- コードをデバッグ実行(F5など)
- ターミナルで、整数8,3,1,6,4,7,10,14,13の順に入力し、最後は入力せずEnter
- 画面左`変数`窓に、現在出力処理中のルートノード(node.value変数)が8であることを確認
- 画面左`コールスタック`窓に、呼出し中のprint_tree関数が1つ積まれていることを確認

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/0a4071f1-5c71-5f66-a01b-628871709901.png)

- 処理続行(F5など)
- ターミナルに、二分探索木のルートノード8が出力される
- 画面左`変数`窓に、現在出力処理中の左の子ノード(node.value変数)が3であることを確認
- 画面左`コールスタック`窓に、print_tree関数が再帰呼出しされ、計2つ積まれていることを確認
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/0d11301a-8654-d946-8170-b966b7c28641.png)

- 処理続行(F5など)
- ターミナルに、二分探索木の左の子ノード3L(Lは左を指す)が出力される
- 画面左`変数`窓に、現在出力処理中の右の子ノード(node.value変数)が1であることを確認
- 画面左`コールスタック`窓に、print_tree関数が更に再帰呼出しされ、計3つ積まれていることを確認
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/8f5412c0-c346-ef74-6953-0f3f3524d6eb.png)

- 処理続行を繰り返すと、最後に全ノードが出力される
```
* 8
** 3L
*** 1L
*** 6R
**** 4L
**** 7R
** 10R
*** 14R
**** 13L
```

## おわりに

再帰呼出しについて、二分探索木を例に、VS Codeコールスタックを用いて理解しました。
コールスタックで、再帰呼出しの各階層を任意選択し、変数窓のノード値を確認することで、
ルートから深さ優先で、各ノードを走査しながら出力する過程を可視化できます。
再帰呼出しの理解にお役立ていただけるとうれしいです。