스택프레임 이란?

public void solution(int n) {
    if(n==0) return;
    else{
        System.out.print(n+" "); //Line 1
        solution(n-1); //Line 2

    }
}

public static void main(String[] args) {
    Main M = new Main();
    Scanner kb = new Scanner(System.in);
    int n = 5;
    M.solution(n);
}

위와 같은 코드일 때, 결괏값은

Output:  5 4 3 2 1 

이다. 예상한 결과이다. n이 5일 때 solution() 함수는 5가 0이 될 때까지 재귀함수를 호출하며 0이 되면 종료된다.

 

그렇다면

public void solution(int n) {
    if(n==0) return;
    else{
        solution(n-1); //Line 1
        System.out.print(n+" "); //Line 2

    }
}

이번에는 solution() 함수에 n이 0이 되면 종료되는 것은 똑같지만 재귀호출을 먼저 실행하고 그다음 n을 출력하도록 코드의 순서를

바꿨다. 그랬더니 결과가

Output: 1 2 3 4 5

가 나왔다. 처음 이 결과를 보고 왜 이 결과가 나왔는지 이해되지 않았다.

이렇게 결과가 나온 이유는 스택프레임이라는 개념 때문이다.

 

스택프레임 이란?

스택프레임이란 함수가 실행될 때 스택형태로  메모리에 저장되는데 함수의 매개 변수, 복귀 주소값, 지역 변수 등이 있지만 중요한 3가지만 기억하면 된다.

위 코드로 예시를 들어보면. n이 5일 때.

main에서 M.solution(n); 을 최초 실행하면 스택프레임에는 아래와 같이 되어있을 것이다. (스택을 표로 표현)

 

매개변수	복귀주소	지역변수
n : 5	Line 1

n==0은 false기에 else문으로 가면

solution(n-1); 이 실행된다. 이때 스택프레임에는 함수가 실행되는 순서대로 스택형태로 정보가 push 된다.

 

매개변수	복귀주소	지역변수
n : 5	Line 1
n : 4	Line 1

 n이 0이 될 때까지 반복한다면 최종적으로는 아래와 같은 형태가 될 것이다.

매개변수	복귀주소	지역변수
n : 1	Line 1
n : 2	Line 1
n : 3	Line 1
n : 4	Line 1
n : 5	Line 1

자 스택최상단인 n:1을 보면 복귀주소가 Line 1이기 때문에 그다음라인인

System.out.print(n+" "); //2

을 실행해야 한다. 그렇다면 결과는 1 이 될 것이다.

1 출력이 실행되고 나면 그다음 라인은 존재하기 않기에 스택에서 pop()될 것이고. 이게 계속 반복되면 결국 

1 2 3 4 5 가 출력되는 것이다.

이 개념을 잘 알고 있어야. 추후 DFS와 같은 알고리즘 개념에서 헤매지 않을 것 같다.