[알고리즘] 재귀함수 스택 프레임(Stack Frame)

 

1. 스택 프레임의 정의

---

 

스택 프레임(Stack Frame)이란 함수가 호출될 때, 그 함수만의 스택 영역을 구분하기 위하여 생성되는 공간이다. 이 공간에는 함수와 관계되는 지역 번수, 매개변수,복귀주소가 저장되며, 함수 호출 시 할당되며, 함수가 종료되면서 소멸한다.

 

이 영역을 표현하기 위해 함수 프롤로그(Prolog)와 함수 에필로그(Epilog)라는 것을 수행한다.

 

(스택 프레임이란 ESP(스택 포인터)가 아닌  EBP(베이스 포인터) 레지스터를 사용하여 스택 내의 로컬 변수, 파라미터, 복귀 주소에 접근하는 기법입니다.)

 

 

 

 

 

 

ESP(스택 포인터): 스택이 현재 어디에 있는지를 가리키는 역할을 하는 레지스터다. (변화함)

EBP: 스택프레임의 시작을 알리는 포인터다. 사실상 스택의 최하단(?).. 을 가리키고 있다고 보면된다.(고정됨)

 

 

 

 

 

위의 복잡한 내용이 헷갈리면 간단히 아래의 그림만 숙지하자.

 

 

 

 

 

 

 

2.재귀함수와 스택프레임

---

      function solution(n) {
        function DFS(L) {
          if (L == 0) return;
          else {
            console.log(L);
            DFS(L - 1);
          }
        }
        DFS(n);
      }
 
      solution(3);

 

다음 함수의 출력순서는

3

2

1

이다.

 

이때 순서를 1 2 3의 순으로 나열하고 싶으면 어떻게 해야할까? 

 

스택을 이용한다면 console.log를 DFS밑에 적어주면 된다.

 

      function solution(n) {
        function DFS(L) {
          if (L == 0) return;
          else {
            DFS(L - 1);
            console.log(L); //위치 변경
          }
        }
        DFS(n);
      }
 
      solution(3);

 

 

DFS(L-1) 밑에 console.log(L)을 적어주면 다음과 같은 순으로 스택이 쌓이게 된다.

 

 

<DFS(0)은 if조건문에 의해 return된다.>

 

복귀주소:  DFS()의 함수내용을 전부 실행한 후 스택프레임이 사라지면서 자기가 호출되었던 주소로 복귀한다.
(여기서는 DFS(n)으로 복귀 후 그 다음줄부터 실행)

 

 

스택의 처리 순서는 LIFO(Last In First Out)이므로 DFS(0)이 리턴된후 DFS(1)의 복귀주소로 돌아간 뒤 6번째 줄인 console.log(L)이 먼저 찍히는 것이다. 

 

그렇게 되면 출력의 순서는 

1

2

3

순으로 나오게 된다.

 

 

이번에는 간단하게 스택프레임과 그것을 이용한 재귀함수에 대해서 알아봤다.

다음에는 이를 더 응용한 이진트리에 대해서 알아볼 것이다.

 

 

 

 

reference:

 

<esp,ebp 구체적인예시>

https://p3ngdump.tistory.com/40

 

https://eliez3r.github.io/post/2019/10/16/study-system.Stack-Frame.html

 

https://welcome-young.tistory.com/61