[크래프톤 정글 5기] 스택, 레지스터, 꼬리 재귀 최적화

스택, push연산, pop연산

 

 

스택(stack)

- 프로시저 호출 시 “지역 변수와 매개변수”를 저장하기 위한 메모리 공간(지역변수 = 로컬변수)

- 후입선출(LIFO, Last In First Out) 구조

 

스택의 용도

- 함수의 로컬 변수 저장 : 각 함수 호출 시, 그 함수의 로컬 변수들이 스택에 저장된다.

- 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다.

- 장점 : 동적으로 메모리 할당/해제 가능, 구현이 간단함, 메모리 관리 overhead가 낮음

 

스택의 특징

- 스택에서 데이터가 삽입되고 빠져나가는 쪽을 top 이라고 한다. 반대쪽은 bottom이다.

- %rsp 레지스터는 스택 포인터이다. 스택 포인터는 항상 스택의 top 주소를 가리키고 있다.

- 스택은 값이 적어짐으로써 성장한다. 즉, 스택 포인터가 0x99 이었다가 0x92가 되면 스택의 크기가 0x07 "증가"한 것이다.

- 따라서 위 그림처럼 스택의 top이 아래로 오도록 표현하면 이해하기 더 쉽다.

 

 

 

레지스터(register)

- 프로세서(CPU) 내부의 고속 작동 메모리

- 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용

 

레지스터의 용도

- 중간 연산 결과의 저장 : 연산 중 생성되는 중간 값을 빠르게 저장/접근하기 위해 사용

- 빠른 데이터 접근 : 특정 데이터나 주소를 빠르게 저장하고 로드하기 위해 사용

- 장점 : 매우 높은 데이터 접근 속도, 데이터를 메모리에서 레지스터로 빠르게 옮길 수 있어 연산 효율 증가

 

 

 

호출 스택 관점에서의, 꼬리 재귀 최적화(Tail Recursion Optimization)

- 호출 스택의 사용을 최적화하는 기법. 재귀함수의 마지막 연산만 호출 스택에 남겨두고, 나머지는 그때그때 스택에서 제거한다.

- 각 함수에서 값을 return 하는 게 아닌, 하위 함수의 인자값으로 전달한다.

 

일반적인 재귀함수

- 일반적인 재귀함수는 return조건에 도달할 때까지 끝없이 하위 함수를 호출한다. 그 과정에서 호출되는 함수들은 모두 스택에 담기게 되고 이는 메모리의 낭비로 이어지며, 스택 오버플로우를 초래할 수 있다.

- 일반 재귀함수는 재귀의 밑바닥 즉, return조건에 도달한 후, 하위부터 함수 하나씩 return하면서 값이 계산된다. 결과적으로 가장 처음에 호출한 함수가 return될때 원하는 결과를 얻을 수 있다.

- 또한, 이 계산 과정에서 스택은 상위 함수의 정보를 전부 담고 있어야 하며, 그동안 스택에서 제거될 수 없다.

 

꼬리 재귀 최적화 재귀함수

- 꼬리 재귀 최적화 형태로 구현하게 되면, 함수가 한번 호출될 때마다 그때그때 값을 계산하여 하위 함수를 재귀호출할 때 해당 값을 인자로 넘겨주게 된다.

- 각 함수가 계산값을 항상 가지고 있기 때문에 가장 밑바닥인 하위 함수에 도착하게 되면 이 시점에 이미 결과가 계산되어 있고, 즉시 값을 리턴하면 된다.

- 때문에 상위 함수에 대한 의존성이 없다. 재귀호출을 한 건 맞지만 상위함수에 대한 정보를 스택에 담아둘 필요가 없기 때문에, 호출 스택이 그때그때 제거되고 메모리의 낭비가 발생하지 않는다.

 

기본 재귀 팩토리얼 함수

int factorial(int n) {

    if (n == 1) {

        return 1;

    }

    return n * factorial(n-1);

}

 

꼬리 재귀 최적화 팩토리얼 함수

int factorialTail(int n, int acc) {

    if (n == 1) {

        return acc;

    }

    return factorialTail(n-1, n*acc);

}

- 꼬리 재귀 최적화 함수는, acc라는 인자에 상위 함수의 계산결과를 받아오고 있다.

- 또한 acc값을 하위 함수를 호출할 때 다시 사용한다.

 

꼬리 재귀 최적화를 처음 들었을 때 만능인 것 같았지만 꼭 그렇지만도 않다.

1. 호출 스택이 쌓이지 않아 스택을 아낄 수 있는 건 맞지만, 결국 연산횟수는 동일하다(시간 복잡도가 거의 비슷하다)

2. 모든 함수에 적용하기 어려울 수 있으며, 구현이 어려울 수 있다.

아마 코딩 테스트 수준에서는 굳이 사용할 필요는 없을 것 같다. 꼭 사용해야 하는 특별한 경우들이 있지 않을까.