재귀 함수와 스택 프레임

코딩 테스트를 준비하면서 완전탐색, DFS, Back tracking 등의 알고리즘 개념을 접하게 되고, 자연스레 스택 프레임(Stack frame)도 접하게 되었습니다. 스택 프레임은 알고리즘 문제에 자주 출시되기 때문에, 이번 기회에 개념을 정확히 알고 넘어가시면 좋을 것 같아요😊

 

Stack Frame

스택 프레임📗

스택 프레임이란 메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개 변수가 저장되는 영역입니다. 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸합니다.

 

함수가 호출되면 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소 값, 함수에서 선언된 지역 변수 등이 저장됩니다. 이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 합니다.

 

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

 

사실 스택 프레임을 처음 접하신 분이라면 위 설명으로 이해가 되지 않을 것 같아요. 쉬운 예시로 다시 한번 설명해보겠습니다.

 

재귀 함수📔

public class Recursive {
    public static void main(String[] args) {
        Recursive T = new Recursive();
        T.DFS(3);
    }

    public void DFS(int n) {
        if(n == 0) {
            return;
        } else {
            System.out.print(n + " ");
            DFS(n-1); 
        }
    }
}

 

위의 결과 값을 예측하기는 어렵지 않습니다. DFS 함수로 인자 값 3이 들어오고, 반복문을 돌듯이 인자 값이 0이 될 때까지 같은 DFS 함수를 계속 호출하게 됩니다. 

3 2 1

 

그러면 System.out.print()를 이용해서 출력하면 위와 같이 3 2 1 순으로 값이 표출 됩니다. 만약 1부터 오름차순으로 표출해야하면 어떻게 할까요?

 

public class Recursive {
    public static void main(String[] args) {
        Recursive T = new Recursive();
        T.DFS(3);
    }

    public void DFS(int n) {
        if(n == 0) {
            return;
        } else {
            DFS(n-1); // line 11
            System.out.print(n + " ");
        }
    }
}

// 결과 : 1 2 3

답은 생각보다 간단합니다. System.out.print() 메서드를 DFS 함수 아래로 위치하기만 하면 됩니다. 이 원리가 바로 스택 프레임입니다. 

 

stack

 

📌 Stack은 LIFO(Last In First Out) 방식으로 가장 나중에 저장된 데이터가 가장 먼저 인출되는 방식으로 동작합니다.

 

1. 처음 인자값으로 3이 들어오고 DFS 함수를 실행합니다. 
2. 0이 아니기 때문에 else문을 타게 되고 다시 한번 DFS(n-1) 함수를 타게 됩니다. 이때, 가장 중요한 것은 처음 DFS(3) 함수는 line 11에서 멈춰 있는 상태로 스택에 쌓이게 됩니다. 쉽게 말하자면 그다음 System.out.print() 메서드가 실행되지 않는 상태로 스택에 쌓인다는 뜻입니다.
3. 그다음은 인자 값으로 2가 들어옵니다. 이번에도 0이 아니기 때문에 2번 문항과 동일하게 실행됩니다. 위 stack 그림처럼 하나씩 계속 인자 값이 0이 될 때까지 쌓이게 됩니다.
4. 마지막으로 DFS() 함수에 0이 들어오게 될 것입니다. 하지만 0일 때는 바로 return 하기 때문에 해당 함수는 바로 종료됩니다. 이후에 스택에 잠시 멈춰있던 함수들이 차례로 실행되게 됩니다. 즉, 마지막으로 쌓였던 인자 값 1부터 실행된다는 뜻입니다.

stack frame 이미지 출처 : http://www.tcpschool.com/c/c_memory_stackframe

위 그림을 보시면 조금 더 이해하시기 수월할 것 같네요😀

 

재귀함수(이진수)📒

가벼운 예시 하나를 더 들어보겠습니다. 10진수 수를 2진수로 반환하기 위한 코드를 구성하려면 재귀 함수를 어떻게 사용해야 할까요?

 

public class Binary {
    public static void main(String[] args) {
        Binary T = new Binary();
        T.DFS(13);
    }

    public void DFS(int n) {
        if(n == 0) {
            return;
        } else {
            DFS(n/2);
            System.out.print(n%2 + " ");
        }
    }
}

// 결과 1 1 0 1

 

원리는 첫 번째 예시와 동일합니다. 10진수를 2진수로 변환하기 위해서는 아래 그림과 같이 2로 나누고 나머지를 누적해야 합니다. 이때도 스택 프레임을 사용하면 쉽게 아래서부터 나머지를 표시할 수 있습니다.

 

2진수 변환

 

팩토리얼(Factorial)📘

팩토리얼은 수학에서 그 수보다 작거나 같은 모든 양의 정수의 곱을 뜻합니다. 알고리즘 공부를 해보신 분이라면 한 번쯤은 접해보셨을 텐데요. 만약 5 팩토리얼을 구한다고 하면 5 * 4 * 3 * 2 * 1 = 120이 결과값입니다.

 

그럼 재귀 함수를 이용해서 팩토리얼 코드를 구성해볼까요?

 

public class Factorial {
    public static void main(String[] args) {
        Factorial T = new Factorial();
        System.out.println(T.DFS(5));
    }
    public int DFS(int n) {
        if(n==1) {
            return 1;
        } else {
            return n*DFS(n-1);
        }
    }
}

// 결과 120

 

사실 재귀를 1에서 멈추는 것 이외에는 위에 예시들과 동일하게 작동합니다. 1에서 멈추는 이유는 팩토리얼은 위에서 언급한 바와 같이 모든 양의 정수의 곱이기 때문입니다.

 

처음 인자 값으로 5가 들어오면 5 * DFS(5-1) -> 스택에 쌓임 그다음으로 4 * DFS(4-1) 스택에 쌓임. 이런 식으로 반복되어서 인자 값이 1이 될 때까지 진행이 되고, 스택이 다 쌓였으면 맨 위의 스택부터 꺼내서 결국엔

 

1 * 2 * 3 * 4 * 5 = 120의 결과를 얻게 됩니다.

 

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

 

마치며

지금까지 재귀 함수와 스택 프레임에 대해 알아보았습니다. 포스팅을 하다 보니 알고리즘 관련으로 포스팅 시리즈를 만들어봐도 괜찮을 것 같네요! 주제가 정해지면 바로 포스팅해보도록 할게요🖐