재귀 함수 사용 시 스택 오버플로가 발생하는 이유는 무엇인가?

함수 호출 시마다 스택 프레임이 생성되어 메모리의 스택 영역을 가득 채우기 때문이다.

가운데 빈 자리를 스택과 힙이 마주 보고 나눠 쓴다. 다만 스택이 힙에 부딪혀 터지는 것은 아니다. 스택마다 쓸 수 있는 크기가 미리 정해져 있고 그 선을 넘는 순간 걸린다.

재귀는 종료 조건에 닿을 때까지 자기 자신을 부르며 스택 프레임을 쌓는다. 각 호출은 이전 상태를 기억해야 하므로 메모리 공간을 계속 점유한다.

탈출 조건이 없거나 깊이가 너무 깊으면 할당된 스택 크기를 초과한다. 이때 런타임 에러인 스택 오버플로가 발생한다.

반복문으로 대체하면 추가적인 스택 프레임 생성이 없어 메모리 효율이 높다. 하지만 트리나 그래프 같은 계층 구조 탐색 시에는 재귀가 가독성이 좋다.