재귀는 문제 구조가 재귀적일 때 유지하고, 비용이 크면 바꾼다

가독성만 보지 말고 종료 조건, 호출 깊이, 중복 계산을 같이 판단해야 합니다.

재귀가 어울리는 경우

구조트리, 그래프, 분할 정복처럼 문제 자체가 작은 같은 문제로 나뉩니다.

종료기저 조건이 짧고 모든 경로에서 명확합니다.

표현반복문보다 문제의 정의를 더 직접적으로 보여 줍니다.

깊이입력 크기만큼 호출이 깊어져 스택 한계가 걱정됩니다.

중복피보나치처럼 같은 입력을 여러 번 다시 계산합니다.

성능함수 호출 비용이 반복문보다 큰 부담이 됩니다.

트리 순회

재귀 유지가 자연스럽습니다.

큰 선형 반복

반복문이 더 안전할 수 있습니다.

중복 하위 문제

메모이제이션 또는 DP를 붙입니다.

A급 판단 기준: 재귀가 아름다운지가 아니라, 종료와 축소가 비용을 이길 만큼 선명한지입니다.