재귀 함수 호출 트리(개념)

[트리]

 

트리

 : 자료구조의 일종이며, 사이클 없이 모든 정점이 연결되어있는 그래프. 정점의 개수가 n개이면 간선의 개수가 n-1개.

 

1. 재귀함수란?
하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 함수.
매 호출마다 입력값(파라미터)가 변화한다.
입력값에 변화가 없거나 특정 패턴을 반복하게 되면 스택 오버 플로우가 발생할 수 있기 때문에 반드시 종료하는 조건이 필요하다.

2. 재귀함수와 for문
한쪽을 다른 한쪽으로 변환이 가능하다.
재귀함수는 함수를 반복적으로 호출하기 때문에 스택 메모리를 사용한다.
반면 반복문은 메모리 힙을 사용한다.

 

스택 : 함수의 호출/반환과 지역변수를 위해 사용.

힙 : 동적으로 메모리 할당을 하기 위한 영역

3. 트리란?
나무와 유사하게 계층적 구조를 띄고 있는 자료구조.
모든 정점이 연결되어있으나 순환하지 않는 것이 특징.
트리의 주된 목적은 탐색

4. 트리문제에 재귀함수를 사용하는 이유
하위 노드가 얼마나 많은 하위 노드를 가질 수 있을지 모르는 경우에 재귀를 사용한다.