재귀함수와 스택프레임

스택프레임은 코딩테스트시 자주 출제되는 개념이기에 공부하고자 작성하였습니다

---

스택프레임

스택 프레임(Stack frame)은 컴퓨터 프로그래밍에서 함수 호출을 관리하기 위한 데이터 구조입니다.

스택 프레임은 함수 호출을 관리하기 위한 데이터 구조로, 함수가 호출될 때마다 스택에 새로운 프레임이 생성되고 실행이 종료되면 스택에서 제거됩니다. 스택 프레임은 함수의 매개 변수, 지역 변수, 반환 주소 등을 저장하며, 스택 자료 구조를 이용하여 구현됩니다.

스택 프레임을 확용하면 함수의 호출이 모두 끝난 뒤에 해당 함수가 호출되기 이전 상태로 되돌아갈 수 있습니다.

 

재귀함수

public class 재귀함수 {
    public void DFS(int n){
        if(n==0) return;
        else{
            System.out.println(n);
            DFS(n-1);
        }
    }

    public static void main(String[] args){
        재귀함수 T = new 재귀함수();
        T.DFS(3);
    }
    
}

위의 결과 값은 DFS 함수로 인자 값 3이 들어오고, 인자 값이 0이 될 때까지 같은 DFS 함수를 호출하게 됩니다.

그렇기 때문에 출력하게 되면 값이 3 2 1 순으로 출력되게 되어집니다.

 

만약 오름차순으로 표현을 원한다면 어떻게 해야할까요?

public class 재귀함수 {
    public void DFS(int n){
        if(n==0) return;
        else{
            DFS(n-1);
            System.out.println(n+" ");
        }
    }
    public void solution(int n){
        DFS(n);
    }

    public static void main(String[] args){
        재귀함수 T = new 재귀함수();
        T.solution(3);
    }
    
}

답은 출력식을 DFS 함수 아래로 위치하기만 하면 되고, 이 원리가 우리가 공부하고있는 스택 프레임입니다.

Stack 출처: programiz.com/dsa/stack

스택(Stack)은 데이터를 일시적으로 저장하기 위한 추상 자료형(Abstract Data Type) 중 하나로, 후입선출(Last In First Out, LIFO) 원칙을 따릅니다.

 

스택은 보통 push와 pop 두 개의 기본 동작을 갖습니다. push는 스택에 데이터를 추가하는 작업이며, pop은 스택에서 데이터를 꺼내는 작업입니다. 스택은 항목을 제거하지 않고 가져오기 위한 peek 기능도 제공합니다.

 

<실행 과정>

 

1. 처음 인자값으로 3이 들어오고 DFS 함수를 실행합니다.

2. 결과값이 0이 아니기 때문에 else문을 통해 다시 DFS(n-1) 함수를 실행합니다. 이 과정에서 처음 DFS(3) 함수는 line11에서 멈춰있는 상태로 스택에 쌓이게 되고, 다음 출력문이 실행되지 않는 상태로 스택이 쌓입니다.

3. 다음은 인자 값으로 2가 들어옵니다. 이번에도 0이 아니기 떄문에 2번과 동일하게 실행이 되고 하나씩 인자 값이 0이 될 때까지 쌓이게 됩니다.

4. 마지막으로 DFS 함수에 0이 들어오게 되고, 0일때는 return을 하기 때문에 해당 함수는 바로 종료됩니다. 이후에 스택에 잠시 멈춰있던 함수들이 차례로 실행되게 되고, 마지막으로 쌓였던 인자 값 1부터 실행됩니다.

 

---