재귀함수와 스택프레임

나 자신을 부르는 재귀함수

 

특이하게도 재귀함수는 "스택영역"에 "스택프레임"을 형성할 수 있다.

메모리의 스택(stack) 영역 :  함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역
스택 프레임(stack frame) : 스택 영역에 차례대로 저장되는 함수의 호출 정보

 

원리 :

함수가 호출되면 -> (매개변수, 지역변수, 복귀주소) 가 메모리에 계속 쌓이다가(push()) -> 끝나면 pop()하면서 소멸

 

이러한 스택 프레임 덕분에 함수의 호출이 모두 끝난 뒤에, 해당 함수가 호출되기 이전 상태로 되돌아갈 수 있다.

import java.util.Scanner;

public class Recursive1 { //재귀함수로 1부터 N까지 출력

	public void DFS(int n) {
		if(n==0) {
			return; //void 타입에서 return;하면 함수 종료의미 
		}else {
			DFS(n-1); //1 줄여서 호출
			System.out.print(n+" "); //출력
		}
	}
	
	public static void main(String[] args) { 		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		Recursive1 rs = new Recursive1();
		rs.DFS(N);
	}
}

---

둘다 재귀인데 위치에 따라 다르게 출력되는 이유?? 

 

1번 -> 123

출력까지 가지 않고 자신을 호출한다

DFS(n-1);  
System.out.print(n+" ");  

2번 -> 321

출력하고 자신을 호출한다

System.out.print(n+" ");  
DFS(n-1);  

재귀 vs for문과 배열 조합 비교했을 때? for문 승리

스택프레임을 사용해서 메모리 낭비도 많이 일어나고 무거워서 성능이 좋지 않다.

 

참고자료

http://tcpschool.com/c/c_memory_stackframe