さいきかんすう

再帰関数は、関数内でその関数を繰り返し呼び出す関数、すなわち、自分の関数を繰り返し呼び出す関数です.再帰関数を繰り返し呼び出す場合は、再帰呼び出しを必要とせずに解決できるbasecaseを決定する必要があります.最小の問題が確定しないと無限ループに陥るので気をつけましょう.

# 1부터 입력된 값까지의 합을 구하는 재귀함수
def recursive_call(num):
	if num < 1:
    	return num
    else:
    	return num + recursive_call(num-1)

再帰関数を繰り返し呼び出すと、より多くのメモリが消費されるので、再帰関数は使用しないでください.しかし,数学的概念が複雑な場合,メモリの使用効率が高くなくても再帰的に問題を解決することが望ましい.

ツリー(Tree)

ツリーはノードが枝のように接続された非線形階層化資料構造である.また、ツリーには他のサブツリーがあり、サブツリーには他のサブツリーがある再帰的なデータ構造でもあります.

用語

バイナリ検索ツリー

ツリーに最大2つのサブノードがあるツリーをバイナリツリーまたはバイナリツリーと呼びます.ここで、バイナリナビゲーションツリー(BST)は、ノードを正確にソートする必要がある特定のタイプのバイナリツリーである.BSTは、単純なバイナリツリーよりも早くノードをナビゲートできるように、値サイズ条件に基づいて値を追加できるバイナリナビゲーションツリーです.
値のサイズの条件は오른쪽 서브 노드(right child)의 값 > 루트 노드(root node or parent node)의 값 > 왼쪽 서브노드(left child)의 값です.また、重複する値を持つノードはありません.
値サイズ条件を決定する理由はBSTが左から右へ探索する構造である.これらの条件により,構造が簡単で,探索速度が単純なバイナリツリーよりも速く,ノードを挿入しやすいなどの特徴がある.

# 이진 검색 트리 구현

class Node:
  def __init__(self,value):
    self.value = value
    self.right = None
    self.left = None

class bst:
  def __init__(self, head):
    self.head = head
  
  def insert_node(self, value):
    self.base_node = self.head

    while True:
      if value < self.base_node.value:
        if self.base_node.left != None:
          self.base_node = self.base_node.left
        else:
          self.base_node.left = Node(value)
          break
      else:
        if self.base_node.right != None:
          self.base_node = self.base_node.right
        else:
          self.base_node.right = Node(value)
          break
  
  def search_node(self, value):
    self.base_node = self.head

    while self.base_node:
      # base node와 찾으려는 값이 일치하면 탐색을 종료함
      if self.base_node.value == value:
        return True
      # 만약 찾으려는 값보다 base node의 값이 크면 왼쪽으로 이동해 탐색함
      elif self.base_node.value > value:
        self.base_node = self.base_node.left
      # 만약 찾으려는 값보다 base node의 값이 크면 오른쪽으로 이동해 탐색함
      elif self.base_node.value < value:
        self.base_node = self.base_node.right
    
    return False