[Algorithm] Java 재귀, 스택 프레임

DFS를 공부하기 전 재귀에 대해 다시 공부해 봤다.
스택 프레임을 그려보며 동작 과정을 보니 좀 더 직관적으로 이해할 수 있었다.
이 공부 과정에 대한 기록이다.

개요

먼저 스택 영역과 스택 프레임에 대해 간략하게 다루고,

대표적인 재귀의 예제인 피보나치수열을 스택 프레임을 그려보며 구현해볼 것이다.

 

그리고 리팩토링을 통해 코드를 개선해 볼 예정이다.

스택 프레임

스택 프레임은 메모리 스택 영역에 저장되는 함수 호출 정보이다.

자바의 메모리 영역 중 스택 영역이 있다.

메모리 영역에 대한 기록은 지난번에 다룬 적이 있다.

[JAVA] JVM 메모리 영역

 

바로 이 스택 영역에 스택 프레임이 쌓이게 되는데

스택 프레임에는 메소드의 매개변수, 복귀 주소, 지역 변수,리턴 값 등 메소드 호출과 관련된 정보가 저장된다.

 

말로는 이해가 힘들어 보인다.

피보나치수열 예제를 스택 프레임 그림과 같이 살펴보자.

피보나치 수열

public static int Fib(int n) {
    if(n==1||n==2)return 1;
    return Fib(n - 1) + Fib(n - 2);
  }

  public static void main(String[] args) {
    int n=5;
    for (int i = 1; i <= n; i++) {
         System.out.print(Fib(i)+" ");
    }
  }

가장 쉽게 피보나치수열을 구현해 봤다.

n이 5일 때 스택 프레임을 그려보며 그 값을 구해보자.

 

처음엔 아래와 같은 스택 프레임이 쌓일 것이다.

편의상 복귀 주소를 line으로 명시했다.

return은 해당 메소드가 반환하는 값이다.

 

위처럼 return 하기 위해서는 Fib 메소드가 다시 호출 되어야 한다.

따라서 스택 프레임이 하나 더 쌓일 것이다.

위와 같이 n이 4일 때의 Fib 메소드 스택 프레임이 쌓였다.

이처럼 반복적으로 return에 필요한 Fib 메소드의 스택 프레임이 계속해서 쌓인다.

 

위의 과정을 반복하고 나면 아래와 같은 스택 영역이 형성될 것이다.

드디어 n이 2가 되어 pop 되는 스택 프레임이 나왔다.

이렇게 필요했던 Fib 메소드의 반환 값이 pop되고

쌓여있던 나머지 스택 프레임도 이러한 과정을 거쳐 모두 pop될 것이다.

 

이를 트리 구조로 나타내보자.

Fib(5)의 값을 구하기 위해 위와 같이 많은 스택 프레임이 쌓이고 pop 된다. 중복되는 Fib 메소드가 보인다. 

만약 n의 크기가 커지게 되면 중복되는 Fib 메소드는 훨씬 많아질 것이다.

 

또한 Fib(1)부터 Fib(5)를 출력하는 것이기 때문에 같은 과정을 더 많이 반복하고 있다.

개선할 점은 아래와 같다.

1. Fib 메소드의 리턴값을 출력할 때, 이미 구한 리턴값이라면 그 값을 출력한다.
2. Fib 메소드 실행 중, 이미 구한 리턴 값이라면 그 값을 사용한다.

배열을 만들어 개선

위 첫 번째 사항을 배열을 이용해 개선해 보자.

static int[] fibo;
  public static int Fib(int n) {
    if(n==1||n==2) {
      fibo[n]=1;
      return 1;
    }
    fibo[n]=Fib(n - 1) + Fib(n - 2);
    return fibo[n];
  }

  public static void main(String[] args) {
    int n=5;
    fibo = new int[n+1];
    Fib(5);
    for (int i = 1; i <= n; i++) {
      System.out.print(fibo[i]+" ");
    }
  }

위처럼 Fib(5)를 먼저 실행해서 n이 1부터 5가 될 때까지의 값을 저장한다.

덕분에 Fib(5)만 실행하면 다른 값들을 구할 수 있어 비교적 효율적인 구현이 가능하다.

 

하지만 아직 위 그림처럼 Fib(5) 내에서 동일한 Fib(n)을 구하기 위한 작업이 반복되고 있다.

메모이제이션으로 이를 개선해 보자.

메모이제이션으로 개선

static int[] fibo;
  public static int Fib(int n) {
    if(fibo[n]>0)return fibo[n];
    if(n==1||n==2) {
      fibo[n]=1;
      return 1;
    }
    fibo[n]=Fib(n - 1) + Fib(n - 2);
    return fibo[n];
  }

  public static void main(String[] args) {
    int n=5;
    fibo = new int[n+1];
    Fib(5);
    for (int i = 1; i <= n; i++) {
      System.out.print(fibo[i]+" ");
    }
  }

위처럼 만약 fibo[n]의 값을 이미 구한 적이 있다면 그 값을 리턴해주도록 했다.

그러면 아래 그림처럼 반복되는 작업을 단축시킬 수 있다.

n이 5이기 때문에 성능 개선이 와닿지 않을 수 있지만

n이 커지면 커질수록 메모이제이션으로 반복되는 작업을 많이 줄일 수 있다.

마치며

위 그림으로 나타낸 스택 영역은 재귀를 이해하기 위해 더 쉽게 직관적으로 나타낸 그림입니다.

 

추가로 피드백이나 잘못된 정보에 대한 지적은 환영입니다.

감사합니다.

출처

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의