서론: 인셉션, 그리고 거울 속의 거울
엘리베이터 거울 양쪽에 서 본 적이 있으신가요? 내 모습이 반대편 거울에 비치고, 그 모습이 다시 내 뒤의 거울에 비치며 끝없이 이어지는 무한의 회랑을 보셨을 겁니다.
컴퓨터 공학에도 이런 기묘한 현상이 존재합니다. 바로 '재귀(Recursion)'입니다. 함수가 다른 함수를 부르는 것이 아니라, 자기 자신이 자기 자신을 다시 호출하는 현상을 말합니다.
영화 <인셉션>에서 꿈속의 꿈으로 들어가듯, 재귀는 코드를 깊은 심연으로 끌고 들어갑니다. 오늘 10편에서는 이 위험하지만 매혹적인 알고리즘이 왜 우주 공학이나 자연의 패턴(프랙탈)을 해석하는 데 필수적인지, 그 수학적 미학을 다뤄보겠습니다.
본론 1: 마트료시카 인형을 여는 법
재귀 함수를 가장 쉽게 이해하는 방법은 러시아 인형 '마트료시카'를 떠올리는 것입니다.
우리의 임무는 "가장 작은 마지막 인형을 찾는 것"입니다.
- 1단계: 인형을 엽니다. 안에 더 작은 인형이 있나요?
- 2단계(재귀): 있다면, 그 작은 인형을 대상으로 다시 1단계(열기)를 반복합니다.
- 3단계: 계속 반복하다가 더 이상 인형이 없으면 멈춥니다.
이것이 재귀의 핵심입니다. 거대한 문제를 똑같은 형태의 더 작은 문제로 쪼개서(Divide), 가장 작아질 때까지 파고드는 것입니다.
본론 2: 반드시 '탈출 조건'이 필요하다
재귀 함수를 설계할 때 가장 중요한 것은 '자신을 호출하는 것'이 아니라 '언제 멈출 것인가'입니다. 이를 기저 조건(Base Case)이라고 합니다.
만약 마트료시카 인형이 무한하게 나온다면 어떻게 될까요? 혹은 거울이 깨지지 않고 영원히 반사된다면요? 컴퓨터는 영원히 계산을 멈추지 못하고 뻗어버릴 것입니다.
NASA의 시스템에서 종료 조건이 없는 재귀 함수는 재앙입니다. 로켓의 연료 계산 프로그램이 끝나지 않고 무한히 돌아간다면, 로켓은 궤도에 진입하기도 전에 통제 불능 상태가 될 것입니다. 그래서 엔지니어는 항상 "가장 마지막 순간(Exit)"을 먼저 정의하고 코드를 짭니다.
본론 3: 스택 오버플로우의 위험성
우리는 지난 4편에서 '스택(Stack) 메모리'를 배웠습니다. 함수가 호출될 때마다 스택에 블록이 쌓인다고 했죠.
그렇다면 재귀 함수가 자기 자신을 1만 번 호출하면 어떻게 될까요? 스택 메모리에 1만 개의 블록이 아파트처럼 쌓이게 됩니다. 메모리 공간은 한정되어 있는데 탑이 너무 높게 쌓이면? 와르르 무너집니다.
이것이 바로 개발자 커뮤니티 이름으로도 유명한 '스택 오버플로우(Stack Overflow)' 오류의 정체입니다. 재귀는 코드를 간결하고 우아하게 만들어주지만, 메모리라는 물리적 비용을 비싸게 치러야 하는 양날의 검입니다.
결론: 우주의 패턴을 닮은 코드
자연계에는 나뭇가지, 번개, 해안선, 은하의 나선팔처럼 전체의 모습이 부분 속에 반복되는 프랙탈(Fractal) 구조가 많습니다. 놀랍게도 재귀 함수는 이러한 자연의 패턴을 코드로 구현하기에 가장 적합한 형태입니다.
재귀를 이해한다는 것은, 단순히 반복문(Loop)을 쓰는 것을 넘어 문제의 본질을 파고드는 수학적 사고력을 갖췄다는 뜻입니다.
이것으로 [Part 2. 시스템을 제어하는 힘] 편이 모두 마무리되었습니다.
지금까지 C언어의 문법과 메모리 구조를 익혔다면, 이제는 외부의 적으로부터 시스템을 지키는 법을 배울 차례입니다. 다음 [Part 3. 보이지 않는 위험과 보안]의 첫 번째 시간, 11편 [버퍼 오버플로우: 해커가 C언어의 빈틈을 파고드는 법]에서 뵙겠습니다.