[면접 준비 - Algorithm]재귀 함수 vs. 반복문

모든 반복문은 언제나 재귀 함수로 변환할 수 있으며, 그 반대도 마찬가지다.

 

따라서 개발자의 필요에 따라 적절히 골라서 사용하는 것이 중요한데, 그 장단점과 차이를 정리해보자.

 

반복문(Iteration)

 

• 선언 - 이 곳에서 반복이 일어난다는 것을 명시. 직관적이며 가독성 좋음.
• 시작 - 초기화, 반복 조건, 제어 변수의 변경, 반복문 내의 명령문 실행에 대한 정보 명시
• 종료 - 특정 조건에 도달 할 때까지 반복적으로 실행
• 무한반복 - 반복 조건에 따라 발생하며 CPU 사이클을 반복적으로 사용
• 메모리 - 힙 메모리 사용(넘칠 시 Out Of Memory 에러 발생)
• 속도 - 빠름
• 변수 - 많음. 이는 변경 가능한 상태의 증가로 이어지며 프로그램 오류가 발생할 가능성이 상대적으로 높음.

재귀 함수(Recursion)

 

• 선언 - 별 다른 선언 없이 호출 시작. 직관적인 이해가 어렵고 가독성 떨어짐.
• 시작 - 일반적으로는 종료 조건만 명시
• 종료 - 스택을 비우며 결과를 전달, 처음 호출된 함수를 반환한다.
• 무한반복 - 종료 조건에 수렴하지 않으면 발생하며 스택 오버플로우를 일으킴
• 메모리 - 스택 메모리 사용(넘칠 시 Stack Overflow 에러 발생)
• 속도 - 느림
• 변수 - 적음. 따라서 코드 길이가 짧고 프로그램 오류의 가능성을 줄임.

하지만 가만 생각해보면 자바 컴파일러는 꼬리 재귀 최적화를 지원하지 않으므로

 

구현하고자 하는 알고리즘이 강력하게 재귀 호출을 요구하지 않는 한 굳이 찾아 쓸 일은 없을 것 같다.