15
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

再帰関数

Posted at

はじめに、 木情報源であったり、決定木アルゴリズムだったり、木構造の再帰を使う機会が多いので、再帰関数についてまとめたいと思います。
自分自身を実行する関数を再帰関数といい、再帰関数内の自分自身の実行箇所を再帰呼び出しと言います。

recursive.ipynb
def recursive_f(depth):
  print("depth: "+ str(depth))
  if depth == 10:
    return 
  recursive_f(depth + 1)

if __name__=="__main__":
  recursive_f(0)

実行結果は次のようになります。
depth: 0
depth: 1
depth: 2
depth: 3
depth: 4
depth: 5
depth: 6
depth: 7
depth: 8
depth: 9
depth: 10

自分自身を呼び出すので、どこかで条件分岐をしてあげなければ無限に実行が続きます。

決定木で実装する時は、ノードクラスを作ってやり、自分の子ノードを格納するメンバ変数を持たせ、自分を分割して子ノードを生成するメンバ関数を再帰関数化してやればいいです。自分の子ノードとなるメンバ変数が、更に孫ノードとなるメンバ変数を持ち、更に曽孫ノードとなるメンバ変数を持ち、、の様に永遠に子ノードを生成します。
簡単のため、深さが3のときの図を表すと、
スクリーンショット 2020-01-21 15.26.30.png

これをコード化してあげると

recursive_tree.ipynb
class Node:
  def __init__(self, max_depth):
    self.left = None
    self.right = None
    self.max_depth = max_depth
    self.depth = None
        
  def split_node(self, depth):
      self.depth = depth
      print("depth: " + str(self.depth))
        
      if self.depth == self.max_depth:
          return

      self.left  = Node(self.max_depth)
      self.right = Node(self.max_depth)

      self.left.split_node(depth + 1)   # recursive call
      self.right.split_node(depth + 1)  # recursive call

if __name__ == "__main__":
    max_depth = 3
    initial_depth = 0

    tree = Node(max_depth)
    tree.split_node(initial_depth)

実行結果
depth: 0
depth: 1
depth: 2
depth: 3
depth: 3
depth: 2
depth: 3
depth: 3
depth: 1
depth: 2
depth: 3
depth: 3
depth: 2
depth: 3
depth: 3
以上が、再帰関数の利用例です。この考え方を身につけると決定木アルゴリズムが実装しやすいのでぜひ試してみましょう。

15
11
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
15
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?