[C/C++] 16. 재귀 함수(1)

앞서 스택 메모리의 동작 방식과 함수 모듈화의 장점을 알아보았다. 이번 글에서는 디버깅 도구인 호출 스택(Call Stack)의 활용법과 함께, 함수가 자기 자신을 다시 호출하는 재귀 함수(Recursive Function)의 동작 원리 및 장단점을 정리한다.

1. 디버깅과 호출 스택(Call Stack)의 시각화

복잡한 프로그램에서 문제(버그)를 추적할 때 눈으로만 코드를 읽는 것은 한계가 있다. Visual Studio 같은 IDE의 디버깅 도구 중 호출 스택(Call Stack)과 로컬(Locals) 창은 메모리의 현재 상태를 파악하는 강력한 무기다.

• 호출 스택: 현재 메모리상에 어떤 함수들이 스택 구조(LIFO)로 쌓여 실행 중인지 실시간으로 보여준다.

• 로컬 창: 호출 스택에서 특정 함수를 클릭하면, 해당 함수 스택에 할당된 지역 변수(Local Variable)들의 현재 값을 확인할 수 있다.

• main()에서 Factorial()을 호출하면 호출 스택에 두 함수가 층층이 쌓여 있는 것을 볼 수 있으며, 동일한 이름의 변수라도 각 함수 스택마다 완전히 독립된 지역 변수로 관리됨을 눈으로 확인할 수 있다.

2. 재귀 함수(Recursive Function)의 동작 원리

재귀 함수란 함수 내부에서 자기 자신을 다시 호출하는 함수를 말한다.

• 일반적인 함수 호출이 다른 함수를 스택에 쌓는 것이라면, 재귀 호출은 완전히 동일한 복사본(새로운 스택 메모리)을 기존 스택 위에 계속해서 쌓아 올리는 것과 같다.

• 따라서 Factorial(4) 안에서 Factorial(3)을 호출하면, 서로 다른 스택 프레임을 가진 두 개의 Factorial 함수가 메모리에 동시에 존재하게 된다.

3. 필수 조건: 탈출 조건과 스택 오버플로우

재귀 함수를 설계할 때 가장 중요한 것은 탈출 조건(Base Case)을 반드시 명시해야 한다는 점이다.

• 스택 오버플로우(Stack Overflow): 만약 탈출 조건이 없거나 잘못 설정되면 함수가 무한히 자신을 호출하게 된다. 결국 운영체제가 프로그램에 할당해 준 스택 메모리의 최대 한계치를 초과하게 되어, 프로그램이 비정상 종료(Crash)되는 치명적인 에러가 발생한다.

• 탈출 조건을 만나면 가장 위쪽에 쌓인 함수부터 차례대로 return을 수행하며 스택에서 제거(Pop)되고, 반환 값은 CPU 레지스터를 거쳐 이전 호출자에게 전달된다.

4. 재귀 함수의 장단점과 활용

재귀 함수는 무조건 좋은 것도, 나쁜 것도 아니며 상황에 맞게 적절히 사용해야 한다.

• 장점 (가독성과 직관성): 수학적 점화식이나 트리(Tree), 디렉토리 구조 같은 계층적 자료구조를 다룰 때 코드가 매우 간결해지고 직관적으로 변한다. 동일한 논리를 반복문으로 구현하려면 별도의 스택(Stack)을 만들어야 해서 코드가 복잡해지는 경우가 많다.

• 단점 (성능 저하와 오버헤드): 함수가 호출되고 반환될 때마다 스택 프레임을 생성하고 매개변수를 복사하는 컨텍스트 스위칭 비용(Overhead)이 발생한다. 단순 반복문(for/while)에 비해 실행 속도가 느려질 수 있다.

마무리하며

• 호출 스택(Call Stack)을 활용하면 현재 실행 중인 함수들의 흐름과 독립적인 지역 변수 상태를 시각적으로 추적할 수 있다.

• 재귀 함수는 자기 자신을 호출하여 새로운 스택을 쌓는 구조이므로, 무한 루프를 막기 위한 탈출 조건이 필수적이다.

• 재귀는 계층 구조 표현에 탁월하여 가독성을 높이지만, 잦은 함수 호출로 인한 성능 저하와 스택 오버플로우 위험을 동반한다.