5.1.2 재귀의 최대 범위와 한계점 기억하기

재귀 호출은 반복 작업을 구현하는 것이기 때문에 재귀의 호출 횟수가 시간 복잡도에 직접적으로 영향을 끼칩니다. 따라서 재귀 호출을 구현할 때는 재귀 호출이 얼마나 수행되는지와 한 번 호출했을 때 어떤 작업을 하는지 잘 따져 보아야 합니다.

재귀 호출의 깊이, 즉 재귀 호출이 얼마나 연쇄적으로 일어나는지는 시간 복잡도 외에도 굉장히 주의 깊게 살펴보아야 할 부분입니다. 재귀 호출을 하면 호출된 메서드에서 사용할 변수들은 메모리에 추가 할당됩니다. 이렇게 메모리가 할당된 변수들은 해당 재귀 호출이 종료되어 더 이상 참조하지 않게 되었을 때 자동으로 메모리에서 할당이 해제됩니다.

재귀 호출이 중간에 종료되지 않고 너무 깊게 들어가 버리면 변수들이 메모리를 모두 할당해서 StackOverflowError 예외가 발생합니다. 이런 예외를 발생시키지 않으려면 재귀 호출의 깊이를 안전하게는 10,000 이하, 아무리 많아도 20,000 이하로 유지시켜야 합니다.