재귀(recursion)란 함수가 자기 자신을 다시 호출하는 프로세스를 의미합니다. 재귀는 하나의 큰 문제를 더 작은 하위 문제들로 나누어 해결할 때 활용됩니다. 다만 한 가지 유의해야 할 점이 있습니다. 각 하위 문제가 모두 동일한 패턴을 따를 때에만 재귀적 접근 방식을 적용할 수 있다는 것입니다.
재귀 함수는 두 가지 서로 다른 부분으로 구성됩니다. 바로 기저 사례(base case)와 재귀 사례(recursive case)입니다. 기저 사례는 재귀 호출을 멈추고 작업을 종료하는 역할을 담당합니다. 만약 기저 사례가 정의되어 있지 않다면, 함수는 이론적으로 무한히 자기 자신을 호출하게 됩니다.
재귀와 스택의 동작 원리
컴퓨터 프로그램에서 어떤 함수를 호출하면, 프로그램은 해당 함수 영역으로 점프하기 전에 현재 프로그램 카운터(program counter)의 값을 내부 스택(internal stack)에 저장합니다. 함수의 작업이 완료되면 저장해 둔 주소를 스택에서 꺼내(pop) 프로그램 카운터에 다시 할당하고, 중단했던 지점부터 작업을 이어갑니다.
재귀 호출이 일어나면 이러한 주소 저장 과정이 여러 번 반복되며, 매번 다음 함수 호출문으로 점프하게 됩니다. 만약 기저 사례가 정의되어 있지 않다면 함수는 끝없이 자기 자신을 호출하면서 주소를 스택에 계속 쌓아 올립니다. 결국 스택에 더 이상 여유 공간이 없어지면 "Internal Stack Overflow"(내부 스택 오버플로) 오류가 발생합니다.
예시: 팩토리얼 계산
재귀 호출의 대표적인 예는 숫자의 팩토리얼(factorial)을 구하는 것입니다. n!은 n * (n-1)!과 같고, 다시 n * (n-1) * (n-2)!과 같습니다. 즉, 팩토리얼이 하나의 함수라면 인자(argument)가 1씩 줄어드는 형태로 계속해서 자기 자신을 호출하게 됩니다. 그리고 인자가 1 또는 0이 되면 1을 반환하는데, 이것이 바로 재귀의 기저 사례가 됩니다.
C++ 코드 예제
#include<iostream>
using namespace std;
long fact(long n){
if(n <= 1)
return 1;
return n * fact(n-1);
}
main(){
cout << "Factorial of 6: " << fact(6);
}실행 결과
Factorial of 6: 720
위 코드에서 fact(6)이 호출되면 6 * fact(5), 5 * fact(4)처럼 호출이 연쇄적으로 이어지다가, n이 1 이하가 되는 순간 1을 반환하며 재귀가 종료됩니다. 최종적으로 6 × 5 × 4 × 3 × 2 × 1 = 720이라는 결과가 출력됩니다. 이처럼 재귀는 문제의 구조가 자기 유사적일 때 코드를 간결하고 직관적으로 만들어 주는 강력한 도구입니다.