[JAVA] 스택프레임 & 재귀함수

 

 

📚 스택프레임 & 재귀함수

 

 

스택 프레임

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

 

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

 

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

 

재귀함수

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)
            System.out.print(n + " ");
        }
    }
}

print 메서드를 DFS 함수 아래로 위치하기만 하면 된다. 이 원리가 바로 스택프레임이다.

 

Stack

스택은 LIFO 방식으로 가장 나중에 저장된 데이터가 먼저 나오게 된다.

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

 

> 추가예시 

팩토리얼

재귀함수를 이용해서 팩토리얼을 구성한다면 ?

public class Factorial {
	public static void main(String[] args){
    	Factorial T = new Factorial();
        System.out.print(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의 결과를 얻는 것이다.