우선 재귀호출을 이해하는데 가장 큰 함점은..
하나의 호출을 두번 부른다고..
같은 함수가 두 번 일을 하는 것이 아니라는 점입니다..
함수를 호출한다는 것을 이렇게 생각하시기 바랍니다..
함수를 하나 만들고 그것을 실행한다..
즉 함수를 선언했다는 것은..
컴퓨터가 함수를 어떻게 만들 것인지에 대한 청사진이라고..
그리고 함수 이름을 하나의 포인터로서 간주를 해보시는 것이죠..

함수 호출이 되면 어떤 일이 벌어질 까?
  1. 함수호출
  2. 메모리에 함수에 해당하는 양을 할당한다. (공간마련)
  3. 함수필요한 데이타를 거기에 넣고 함수의 맨 앞부분 부터 실행한다.
  4. 실행이 끝나면 할당 받은 메모리를 회수한다. (방빼!)

그런데 위의 상황에서..
4번이 되기 전에 함수가 호출이 더 되면??
메모리에 함수가 두개가 생기는 것이죠..
아래는 수학의 n!를 구하는 C++ Builder 소스 예제입니다..

int Fact(int n)
{
  if (n > 1) return (Fact(n-1)*n);
  else return (1);
}

void __fastcall TForm1::Button1Click(TObject *Sender)
{
  ShowMessage(IntToStr(Fact(3)));
}

위의 상황에서 Fact(3)를 하나씩 추적해 보겠습니다..
  1. Fact(3) : n이 1 보다 크니, Fact(2) 실행..
     메모리에는 Fact(3), Fact(2)이 존재
  2. Fact(2) : n이 1 보다 크니, Fact(1) 실행..
     메모리에는 Fact(3), Fact(2), Fact(1)이 존재
  3. Fact(1) : n이 1 보다 크지 않으니 1을 리턴하고 종료
     메모리에는 Fact(3), Fact(2)이 존재
  4. Fact(2)는 Fact(1)의 리턴값 * 2를 리턴하고 종료, (1)*2
     메모리에는 Fact(3)이 존재
  5. Fact(3)은 Fact(2)의 리턴값 * 3을 리턴하고 종료, (1*2)*3
     메모리에는 남은 것이 없음
  6. 화면에 결과값이 출력됨

즉, 함수가 다른 함수를 실해하면..
자기 자신이라도 메모리에 마지막 실행부분이 남았다가..
다시 부른(재귀호출) 자신인 함수나 다른 함수가 종료되면..
그 뒤에서 부터 다시 시작합니다..


From 류..