재귀 함수의 작동 원리를 이해하기 위해서는 함수 호출과 호출 스택(Call Stack)의 개념을 이해해야 합니다. 재귀 함수는 함수 내에서 자기 자신을 호출하므로 호출 스택이 어떻게 작동하는지 살펴보겠습니다.

1. 재귀 함수 호출:

   • 재귀 함수는 자신을 호출합니다. 즉, 함수 내에서 동일한 함수를 다시 호출하는 것이 재귀 호출입니다.
   • 이때 함수 호출은 인자와 함께 새로운 실행 컨텍스트를 생성하고 현재 실행 중인 함수의 실행을 일시 중단합니다.

2. 호출 스택 (Call Stack):

   • 호출 스택은 함수 호출의 순서와 컨텍스트를 추적하는 스택 자료 구조입니다.
   • 재귀 함수가 호출되면 현재 함수의 실행 컨텍스트가 스택에 푸시(push)됩니다.
   • 새로운 함수 호출이 발생하면 해당 함수의 실행 컨텍스트가 스택에 추가됩니다.

3. 종료 조건 (Base Case):

   • 재귀 함수는 종료 조건을 갖고 있어야 합니다. 종료 조건은 재귀 호출을 멈추는 조건입니다.
   • 종료 조건이 충족되면 재귀 함수가 스택에서 팝(pop)되고 결과값을 반환합니다.

4. 재귀 호출의 해결:

   • 재귀 함수는 종료 조건을 만족하지 않을 때 작은 부분 문제로 나누고, 이를 해결하기 위해 자기 자신을 재귀적으로 호출합니다.
   • 작은 부분 문제가 해결되면 그 결과를 조합하여 원래 문제를 해결합니다.
   • 재귀 호출이 깊이 들어갈수록 스택에 더 많은 실행 컨텍스트가 쌓이게 됩니다.

5. 재귀 호출의 종료:

   • 종료 조건이 충족되면 재귀 호출이 중단되고, 스택에서 함수 호출이 순차적으로 팝되며 결과값이 반환됩니다.
   • 이 과정은 호출 스택이 모두 비워질 때까지 반복됩니다.

재귀 함수의 작동 원리를 요약하면, 함수가 자기 자신을 호출하면서 스택에 실행 컨텍스트를 쌓고, 종료 조건에 도달하면 스택에서 팝되어 결과를 반환하는 과정을 반복합니다. 이를 통해 재귀 함수는 복잡한 문제를 간단한 부분 문제로 분해하고 해결할 수 있습니다.