재귀 함수

재귀(Recursion)는 어떤 것을 정의할 때 자기 자신을 참조하는 행위를 뜻한다. 프로그래밍에서 재귀 함수는 함수가 실행 과정에서 자기 자신을 다시 호출하는 형태로 구현된다. 이는 복잡한 문제를 간단한 단위 동작과 그 동작을 반복하는 하위 문제로 단순화할 수 있을 때 유용하다. 앨런 튜링과 알론조 처치의 연구 등 초기 컴퓨터 과학의 기초 형성 시기부터 핵심적인 개념으로 다루어졌다.

재귀 함수가 올바르게 작동하고 무한 루프에 빠지지 않기 위해서는 반드시 다음 두 가지 요소를 포함해야 한다.

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

예를 들어 팩토리얼 함수 $f(n)$에서 $n=0$일 때 1을 반환하는 것이 기본 사례이며, $n > 0$일 때 $n \times f(n-1)$을 계산하는 것이 재귀 사례이다.

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

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

• 직접 재귀 (Direct Recursion): 함수가 자기 자신을 직접 호출하는 가장 일반적인 형태이다.
• 간접 재귀 (Indirect Recursion): 함수 A가 함수 B를 호출하고, 함수 B가 다시 함수 A를 호출하는 식으로 두 개 이상의 함수가 순환적으로 호출되는 형태이다.
• 꼬리 재귀 (Tail Recursion): 재귀 호출이 함수의 마지막 연산으로 이루어지는 형태이다. 일부 컴파일러는 이를 최적화하여 스택 오버플로우를 방지한다.

재귀와 반복문(for, while)은 많은 경우 서로 대체가 가능하다.

재귀 함수는 호출 스택의 크기에 제한을 받는다. 대부분의 실행 환경에서는 최대 호출 스택 크기가 정해져 있으며, 이를 초과할 경우 스택 오버플로우(Stack Overflow) 에러가 발생하며 프로그램이 종료된다. 또한 동일한 계산을 반복하는 경우 성능이 저하될 수 있으므로, 이를 해결하기 위해 **메모이제이션(Memoization)**이나 동적 계획법을 함께 사용하기도 한다.