재귀 함수

자신을 호출하는 방식으로 동작하는 함수

 

문제를 더 작은 하위 문제로 분할하여 해결하는 분할 정복 알고리즘에 사용된다. 

자기 자신을 호출하기 때문에 특정 상황에서의 종료 조건과 재귀 조건을 가져야한다.

 

재귀함수의 장점

• 코드를 간결하게 만든다.
• 문제를 세분화하여 접근 가능하다.

재귀함수 단점

• 재귀함수가 호출될 때 마다 스택에 메모리가 할당되어 메모리를 많이 차지할 수 있다.
• 함수의 호출에 따른 메모리 접근에 의해 오버헤드 비용이 반복문에 비해 더 크다.
• 재귀 함수를 막 사용하면 함수의 논리 이해가 어려워 질 수 있다.

재귀 함수의 성능 향상을 위한 최적화

• 종료 및 진입 조건을 설정하여 재귀 호출의 횟수를 조절한다.
• 재귀 함수 구문의 마지막 부분에서 재귀 호출하여, 스텍 프레임을 재사용하는 방식
• 메모이제이션 기능을 활용하여 반복되는 결과를 캐싱해두어 재귀 횟수를 조절한다.
• 꼬리 재귀 최적화를 이용하여 스택 프레임을 재사용하여 컴파일러가 함수 호출을 1번만하게 만든다.