[Algorithm] Stack 과 Recursive

Recursive는 상당히 많은 알고리즘 문제나 면접문제에 나오는 알고리즘 이지만 사실 거시적 소프트웨어 구현측면에서는 잘 사용하지 않는 기법이다. 이유는 

• 사용되는 메모리 스택의 크기를 가늠하기 어렵고 
• 스택 오버플로을 컨트롤하기 어렵다.
• 모니터링 또한 어렵다.

위의 내용을 이해하기 위해 recursive가 무언가에 대해 얘기하자면... 유명한 N!을 구하는 프로그램을 짜보자

 

N! = N * (N-1) * (N-2) * ... * 2 * 1

 

이걸 조금 바꿔보면 

N! = N * (N-1)! 

이지용?

이를 코드로 구현하면 ...

int factorial(int n){
    if(n == 1) return 1;
    return n * factorial(n-1)
}

N!를 구하는 문제가 간단한 4줄로 구현되었다. 

이코드에 stack의 S도 나오지 않았지만 실제는 stack이 사용되었다.

 

compiler는 function call시 현재의 argument를 stack에 저장하고 새로운 function으로 진입한다.

함수가 리턴되면 저장된 argument를 pop하여 현재의 local 변수들도 대체하고 연산을 수행한다.

결국은 n==1이 될때까지 stack에 저장하고 순차적으로 n!를 계산한다.

 

여기서 문제는 stack은 compiler에 의해 관리된다는 점이고 heap영역과 공유되기 때문에 깊이가 깊어지면 stack overflow과 발생하고 panic에 빠지는데 control할수있는 방법이 없다. 실행되는 시점에 남은 stack영역을 check하기도 쉽지 않으며 ... abort또한 어렵다.

배보다 배꼽이 더 큰 상황???

 

사실 N!의 경우 for문으로 간단히 계산할수있지만 recursive와 stack에 대한 내용이므로 어렵게 stack을 이용한 방법으로 바꿔 보겠다.

void push(int n);
int pop(); // returns -1 if stack is empty

int factorial(int n){
    while(n > 1){
    	push(n--);
    }
    
    int n;
    int result = 1;
    while((n=pop()) > 0){
    	result *= n;
    }
    
    return result;
}

n==1이 될때까지 stack에 넣은후 반대순서로 pop하여 곱하는 간단하고 비효율적(?!!)인 코드입니다.

recursive와의 차이점은 stack이 user level에 관리되고 overflow시 user level에서 관리가 가능하다는 점이 다름니다.

 

실제로 실무에서는 user level에 관리되는 형태로 많이 쓰입니다.

개념만 이해합시다. 실무에서는 응용력!! 이니까.!!!

 

PS : 실제로 N!를 구현한다면 단순히 for loop를 사용할 껍니다.

int factorial(int n){
    int result = 1;
    for(int i = 2; i <= n; i++){
    	result = result*i;
    }
    return result;
}