자기 자신을 부르는 함수
C 함수가 자기 자신을 부르는 것을 막는 것은 없습니다. 자기 이름이 본문 안에서 스코프에 있으므로 이것은 합법입니다.
void countdown(int n) {
printf("%d\n", n);
countdown(n - 1); /* 자기를 부른다 - 그런데 멈추지 않는다! */
}
동시에 망가져 있습니다. 영원히, 음수로 내려가며 출력하다가 프로그램이 죽습니다. 빠진 것은 기저 사례입니다. 함수가 자기를 부르지 않고 반환하는 조건 말입니다.
모든 재귀 함수에는 정확히 이 두 부분이 있습니다.
- 기저 사례 - 가장 작은 입력으로, 더 이상의 호출 없이 바로 답합니다.
- 재귀 사례 - 자기 자신의 엄격히 더 작은 판으로 문제를 풉니다.
"엄격히 더 작은"이 사람들이 틀리는 부분입니다. countdown(n - 1)은 호출마다 0을 향해 갑니다. countdown(n)은 그러지 않고, n이 영원히 1일 수 있다면 countdown(n / 2)도 그렇습니다. 모든 경로가 문제를 줄여야 하며, 아니면 기저 사례에 결코 닿지 못합니다.
팩토리얼
표준적인 첫 예제입니다. n!은 n × (n-1) × ... × 1이고, 0!은 1로 정의됩니다. 그 정의 자체가 이미 재귀적입니다. n! = n × (n-1)!이죠.
답이 어떻게 조립되는지 보려면 factorial(4)를 따라가 보세요. 호출은 내려가고, 곱셈은 올라오는 길에 일어납니다.
factorial(4) -> 4 * factorial(3)
factorial(3) -> 3 * factorial(2)
factorial(2) -> 2 * factorial(1)
factorial(1) -> 1 (기저 사례)
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
기저 사례가 반환할 때까지 아무것도 곱해지지 않습니다. 대기 중인 모든 호출이 각자의 n을 쥔 채 기다리고 있고, 그것이 몸에 익혀야 할 점입니다. 기다리는 그 호출들이 메모리를 차지합니다.
반환 타입을 보세요. int는 13! 근처에서 넘쳐 조용히 틀린 숫자를 만들어 냅니다. C는 검사하지 않습니다. unsigned long long은 20!까지 가고 그 이상은 못 갑니다. 21!이 64비트를 넘기 때문입니다. 여기서 한계 요인은 재귀가 아니라 타입입니다.
기저 사례가 n == 1이 아니라 n <= 1인 것은 의도적입니다. factorial(0)은 1이어야 하고 <=가 그것을 처리합니다. n == 1이었다면 factorial(0) 호출이 -1, -2로 재귀해 끝나지 않습니다. "명백히 맞아 보이는" 기저 사례가 어떻게 입력 하나를 놓칠 수 있는지 잘 보여 줍니다.
피보나치, 그리고 순진한 판이 함정인 이유
피보나치는 또 다른 고전입니다. 각 숫자는 앞선 둘의 합이고, 0과 1에서 시작합니다. 재귀 정의가 저절로 쓰입니다.
호출 횟수를 보세요. fib(10)은 177번, fib(35)는 거의 3천만 번입니다. 5씩 올라갈 때마다 일이 약 열한 배가 됩니다.
이유는 호출 트리에 드러납니다. fib(5)가 fib(4)와 fib(3)을 부르고, fib(4)가 fib(3)을 또 부르고, 그 각각이 fib(2)를 처음부터 다시 계산합니다. 아무것도 기억되지 않으므로 같은 부분 문제가 거듭 풀리고, 호출 수가 대략 1.6ⁿ처럼 자랍니다. 이 방식의 fib(50)은 며칠을 돌 것이고, fib(100)은 우주보다 오래 갈 것입니다.
반복문 판은 마지막 두 값을 기억하며 선형입니다.
fib(90)이 즉시 반환합니다. 교훈은 "재귀가 느리다"가 아니라, 겹치는 부분 문제가 있는 재귀는 답을 기억하지 않는 한 느리다는 것입니다. 계산하면서 결과를 배열에 저장하면(메모이제이션) 재귀 판도 선형이 됩니다.
호출 스택과 스택 오버플로
모든 함수 호출은 매개변수와 지역 변수, 그리고 돌아갈 주소를 둘 곳이 필요합니다. 그 저장 공간이 스택 프레임이고, 호출이 시작될 때 쌓이고 반환할 때 걷힙니다. 재귀는 프레임을 차곡차곡 쌓습니다. factorial(1000)은 각자의 n을 가진 천 개의 프레임을 동시에 살려 둡니다.
스택은 크지 않습니다. 보통의 기본값이 1~8MB라, 현실적인 한계는 프레임 수만 개 정도이고 각 프레임이 큰 지역 배열을 담으면 훨씬 적습니다. 넘어서면 프로그램이 죽습니다.
Segmentation fault (core dumped)
그것이 스택 오버플로이고, 만나는 길은 둘입니다.
무한 재귀 - 기저 사례가 없거나 닿을 수 없는 경우입니다. 이것은 버그이고, 크래시는 즉각적입니다.
int bad(int n) {
return bad(n - 1); /* 기저 사례가 없다 - 순식간에 죽는다 */
}
올바르지만 너무 깊은 경우 - 백만 항목짜리 목록에서 원소마다 한 번씩 재귀하는 것입니다. 논리는 맞지만 그 접근이 스택에 들어가지 않습니다. 반복문으로 다시 쓰거나, 깊이가 로그가 되도록 구조를 바꾸세요(이진 탐색과 병합 정렬이 하듯 절반씩 재귀하면 백만 항목에 깊이가 약 20입니다).
어떤 컴파일러는 꼬리 재귀 - 재귀 호출이 함수가 하는 맨 마지막 일이고 그 뒤에 남은 작업이 없는 경우 - 를 반복문으로 바꿔 프레임 하나를 재사용할 수 있습니다. 위의 countdown은 꼬리 재귀이고, factorial은 아닙니다. 호출이 반환한 뒤에도 곱셈이 남아 있으니까요. 하지만 C는 이 최적화를 요구하지 않으므로, 컴파일러와 플래그에 따라 일어날 수도 있고 아닐 수도 있습니다. 최적화기가 꼬리 호출을 없애 줘야만 동작하는 C는 절대 쓰지 마세요.
재귀가 진짜로 이기는 곳
모든 재귀 함수는 반복문으로 다시 쓸 수 있고, 단순한 세기에는 반복문이 확실히 낫습니다. 재귀가 값을 하는 것은 데이터 자체가 재귀적일 때, 즉 구조가 자기 자신의 더 작은 사본을 담고 있을 때입니다.
이진 탐색이 깔끔한 예입니다. 절반을 탐색하고, 그 절반을 다시 탐색합니다.
여기에는 기저 사례가 둘인데 흔한 일입니다. 하나는 성공, 하나는 소진입니다. 깊이는 약 log₂(n)이라, 십억 개 원소라도 프레임 서른 개면 됩니다.
재귀가 자연스럽게 맞는 다른 곳들. 트리나 연결 리스트 걷기, 디렉터리 순회, 중첩된 식 파싱, 그리고 퀵 정렬과 병합 정렬 같은 분할 정복 정렬입니다. 이 모두에서 재귀 코드는 그것을 대체할 명시적 스택이 있는 반복문보다 짧고 동시에 명확합니다.
재귀인가 반복문인가?
반복문을 쓸 때 문제가 선형일 때 - 세기, 합하기, 훑기
재귀를 쓸 때 데이터가 중첩되어 있을 때 - 트리, 중첩 구조, 분할 정복
재귀를 다시 쓸 때 깊이가 입력 크기에 따라 끝없이 자랄 수 있을 때
절대 재귀를 쓰지 말 때 부분 문제가 겹칠 때, 메모이제이션을 하지 않는 한
실용적인 메모 둘. 재귀 호출은 반복 한 번보다 조금 더 비쌉니다. 매번 프레임을 쌓고 걷어야 하니까요. 그래서 자주 도는 단순한 반복문에서는 반복 판이 메모리뿐 아니라 속도에서도 이깁니다. 그리고 디버깅이 다릅니다. 깊은 재귀의 스택 추적은 똑같아 보이는 프레임 수백 개이므로, 무언가 끝나지 않을 때는 (위의 calls 카운터처럼) 진입 시 매개변수를 출력하세요.
재귀 함수 쓰기: 체크리스트
- 기저 사례를 먼저 찾으세요. 가장 작은 입력은 무엇이고 그 답은 무엇인가? 그것을 말할 수 없다면 함수를 쓸 수 없습니다.
- 재귀 호출이 동작한다고 가정하세요. 머릿속으로 따라가지 말고,
factorial(n - 1)이(n-1)!을 반환한다고 믿은 뒤 그것을 답으로 바꾸는 한 단계를 쓰세요. - 모든 경로가 줄어드는지 확인하세요. 각 재귀 호출은 0과 음수를 포함한 모든 가능한 입력에 대해 기저 사례 쪽으로 움직여야 합니다.
- 깊이를 확인하세요. 실제 데이터에서 대략 몇 프레임 깊이까지 갈까요? 수천은 괜찮고 수백만은 아닙니다.
- 겹침을 확인하세요. 같은 부분 문제가 두 번 계산된다면 메모이제이션이나 반복문이 필요합니다.
자주 묻는 질문
C에서 재귀란 무엇인가요?
같은 문제의 더 작은 판을 풀려고 자기 자신을 부르는 함수입니다. 모든 재귀 함수에는 두 가지가 필요합니다. 재귀하지 않고 반환하는 기저 사례와, 거기에 눈에 띄게 가까워지는 재귀 사례입니다. 기저 사례가 없으면 호출이 멈추지 않고 프로그램이 스택 오버플로로 죽습니다.
C에서 팩토리얼 함수는 어떻게 쓰나요?
int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }입니다. 기저 사례가 0과 1을 처리하고, 각 재귀 호출이 n을 1씩 줄여 거기에 도달합니다. int는 13!에서 넘치므로 더 큰 값에는 unsigned long long을 쓰세요.
C에서 재귀 피보나치는 왜 그렇게 느린가요?
fib(n)이 fib(n-1)과 fib(n-2)를 부르고, 그것들이 같은 부분 문제를 거듭 다시 계산하기 때문입니다. 호출 수가 지수적으로 자라서 fib(50)은 몇 년이 걸립니다. 마지막 두 값을 기억하는 반복문으로 다시 쓰면 선형이 되고 즉시 끝납니다.
C 재귀에서 스택 오버플로의 원인은 무엇인가요?
호출마다 매개변수와 지역 변수를 위한 스택 프레임을 차지하는데, 스택은 몇 메가바이트뿐입니다. 기저 사례가 없거나 닿을 수 없으면 무한 재귀가 되어 즉시 죽습니다. 올바른 재귀라도 수십만 단계 깊이로 들어가면 스택을 다 쓸 수 있습니다.
