[면접 준비 - Algorithm]재귀, 재귀 함수

재귀란 일반적으로 정의하자면 자기 언급이다.

 

수학으로 봤을 땐 일종의 점화식이라고 할 수 있으며,

 

프로그래밍적으로 이야기하자면 재귀 함수란 정의 단계에서 자시 자신을 호출하는 함수를 가리킨다.

 

주어진 문제를 풀 때 자기 자신을 다시 호출함으로써 코드의 복잡도를 줄이기 위해 사용한다.

 

하지만 꼬리재귀 최적화가 되어있지 않은 환경에서 재귀 호출은 스택 메모리를 빠르게 잡아먹게 되므로

 

실행 속도 측면에서 반복문이 더 좋은 선택이 된다.

 

여기서 꼬리재귀 최적화란 메서드를 재귀 호출 메서드와 꼬리 메서드로 구분해

 

재귀 호출 이후 추가적인 연산을 실행하지 않도록 막는 방법이며,

 

C++, Swift, Kotlin 컴파일러에는 자동으로 구현되어 있으나 보안상의 이유로 자바 컴파일러엔 구현되지 않았다.

 

다만 이에 영향을 받은 함수형 언어를 받아들인 람다식, 함수형 인터페이스로 비슷한 구현을 할 수는 있다.

 

추가로 함수형 인터페이스란 단 한 개의 추상 메서드를 갖는, 람다식을 위한 인터페이스를 말한다.