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

はじめに

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

再帰呼出し(recursive call)とは

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

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

二分木と二分探索木とは

• 二分木(binary tree)とは

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

• 二分探索木(binary search tree)

  • 左の子孫の値 ≤ 親の値 ≤ 右の子孫の値 という制約を持つ二分木
    

※ 引用元: 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つ積まれていることを確認

• 処理続行(F5など)

• ターミナルに、二分探索木のルートノード8が出力される

• 画面左変数窓に、現在出力処理中の左の子ノード(node.value変数)が3であることを確認

• 画面左コールスタック窓に、print_tree関数が再帰呼出しされ、計2つ積まれていることを確認
  

• 処理続行(F5など)

• ターミナルに、二分探索木の左の子ノード3L(Lは左を指す)が出力される

• 画面左変数窓に、現在出力処理中の右の子ノード(node.value変数)が1であることを確認

• 画面左コールスタック窓に、print_tree関数が更に再帰呼出しされ、計3つ積まれていることを確認
  

• 処理続行を繰り返すと、最後に全ノードが出力される

* 8
** 3L
*** 1L
*** 6R
**** 4L
**** 7R
** 10R
*** 14R
**** 13L

おわりに

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