재귀 & 트리

재귀함수

• 자신을 정의할 때 자기 자신을 재참조 하는 함수
• recurrence relation(점화식), base case로 구성됨

recurrence relation

• f(n)을 f(n-1), f(n-2), ... f(2), f(1)의관계식으로 표현한 것
• ex) Factorial: f(n) = n * f(n-1)

base case

• 더이상 재귀호출을 하지 않아도 계산값을 반활할 수 있는 상황(조건)
• 모든 입력이 최종적으로 base case를 이용해서 문제를 해결
• 무한 루프 방지

재귀함수의 시간 복잡도

• 재귀함수 전체 시간복잡도 = 재귀함수 호출 수 x (재귀 함수 하나 당) 시간복잡도
• O(n)의 시간복잡도
  f(n) = f(n-1) + n 
  
  O(2^n)의 시간복잡도
  f(n) = f(n-1) + f(n-2)
  
  O(log2의n)의 시간복잡도
  binary search

트리

• 서로 연결된 Node의 계층형 자료구조
• root와 부모-자식 관계의 subtree로 구성

• 

이진 트리(Binary Tree)

• 모든 노드의 차수가 2 이하인 트리
• Value와 LC(Left Child 노드의 주소값), RC(Right Child 노드의 주소값)으로 구성

완전 이진 트리(Complete Binary Tree)

• 마지막 레벨(맨 밑)을 제외하고 모두 순차적으로 채워져 있는 트리
• 

 

참고자료

https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC

https://velog.io/@keum0821/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B0%9C%EB%85%90%EA%B3%BC-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC

https://heytech.tistory.com/105