재귀의 동작원리는 무엇일까??
재귀함수의 동작원리를 이해하기 위해서는 메모리 주소와 변수 이름들이 어떻게 결합되는지를 알 필요가 있다.
바인딩
메모리 주소와 변수 이름간의 결합을 바인딩(binding)라 한다. 그리고 컴파일/실행사이클 동안 바인딩이 발생한 시점을 바인딩시간이라 하는데 이때 바인딩 시점에 따라 정적 기억장소 할당, 동적기억장소 할당으로 나눌 수 있다. 이름에서 볼수 있듯이 정적 기억장소 할당은 컴파일시에, 동적 기억장소 할당으 런타임에 이뤄진다. 이때 중점적으로 고려해야할 사항은 “언제 함수의 인자가 메모리 상의 특정 번지에 바인딩되는가?”로 질문의 답에 따라 재귀함수의 지원여부가 결정된다.
정적 기억 장소 할당
프로그램이 번역 될때 컴파일러는 심볼 테이블을 생성하고 변수명과 메모리주소를 기록한다. 그럼 함수의 인자는 어디에 저장될까? 실제로 함수명의 옆 빈공간에 저장한다
void func(int cnt,int cnt2){
}
위의 경우 cnt는 func-1, cnt2는 func-2에 할당
각 인자와 지역변수는 컴파일 시에 단지 하나의 위치가 할당된다. 그럼 재귀호출에 의해 생성되는 인자와 지역변수의 여러 버전은 어디에 저장될까?
동적 기억장소 할당
컴파일러는 변수를 실제주소가 아닌 상대 주소로 참조한다. 이때 컴파일러는 함수의 인자나 지역 변수를 참조할 때 함수 코드의 위치에 상대적인 위치가 아닌 런타임 시에 알 수 있는 주소에 대한 상대적인 위치를 참조한다는 점이다. 함수가 호출될때 인자, 지역변수, 반환 번지를 유지하는 공간이 필요하다. 이들을 저장할 작업 영역을 활성레코드 혹은 스택 프레임이라 부른다. 재귀 함수를 포함하여 함수가 호출될 때는 새로운 활성 레코드가 생성된다. 따라서 각각의 값은 이 활성 레코드의 값을 참조하여 사용한다. 이 활성 레코드는 함수가 종료될 때 해제된다.
struct ActivationRecordType{
AddressType returnAddr;
int result;
int number;
}
또한 함수 호출시 생성되는 활성 레코드는 LIFO규칙에 따르는 런타임 스택에 푸시되고 활성 레코드를 추적한다.
호출을 거듭할 수록 런타임 스택에 활성 레코드가 쌓이고 코드를 수행하며 알맞은 반환 값을 반환번지로 옮겨간다. 함수1개의 수행이 끝나면 런타임 스택에서 pop되고 반환값이 그 전 함수의 반환번지로 옮겨간다.
