재귀 함수

재귀는 어떤 것을 정의할 때 자기 자신을 참조하는 행위를 뜻한다. 프로그래밍에서 재귀 함수는 함수가 실행 과정에서 자기 자신을 다시 호출하는 형태로 구현된다. 이는 복잡한 문제를 간단한 단위 동작과 그 동작을 반복하는 하위 문제로 단순화할 수 있을 때 유용하게 사용된다.

재귀 함수가 올바르게 작동하기 위해서는 반드시 다음의 두 가지 요소를 포함해야 한다.

• 기본 사례 (Base Case): 재귀 호출을 중단하고 결과를 반환하는 종료 조건이다. 이 조건이 없거나 충족되지 않으면 함수가 무한히 호출된다.
• 재귀 사례 (Recursive Case): 문제를 더 작은 단위로 쪼개어 자기 자신을 다시 호출하는 부분이다. 호출이 반복될수록 입력값은 점차 기본 사례에 가까워져야 한다.

재귀 함수는 메모리의 호출 스택(Call Stack) 구조를 이용한다. 함수가 호출될 때마다 매개변수, 지역 변수, 복귀 주소 등의 정보가 스택에 쌓인다.

1. 함수가 자기 자신을 호출하면 새로운 실행 컨텍스트가 스택에 추가된다.
2. 기본 사례에 도달할 때까지 스택은 계속 깊어진다.
3. 종료 조건이 만족되면 가장 마지막에 호출된 함수부터 결과값을 반환하며 스택에서 제거(LIFO)된다.
4. 최종적으로 처음 호출된 함수까지 결과가 전달되며 전체 연산이 마무리된다.

재귀와 반복문(for, while)은 많은 경우 서로 대체가 가능하다. 두 방식의 특징은 다음과 같다.

재귀 함수는 수학적 정의나 계층적 자료구조를 다룰 때 자주 사용된다.

• 팩토리얼(Factorial): $n! = n \times (n-1)!$ (단, $0! = 1$)
• 거듭제곱: $x^n = x \times x^{n-1}$
• 기타: 피보나치 수열, 트리(Tree) 탐색, 하노이의 탑 문제 해결 등

재귀 함수는 호출 스택의 크기에 제한을 받는다. 대부분의 런타임 환경에서는 최대 호출 스택 크기가 정해져 있으며, 이를 초과할 경우 스택 오버플로우(Stack Overflow) 에러가 발생하며 프로그램이 강제 종료된다. 따라서 깊은 재귀가 필요한 경우에는 반복문을 사용하거나 꼬리 재귀 최적화 등의 기법을 고려해야 한다.