피보나치수열(재귀,메모이제이션)

문제

N항 까지의 피보나치 수열을 출력하기.

나의 풀이

class Main2 {
	public int DFS(int n) {
		if(n==1) return 1;
		else if(n==2) return 1;
		else return DFS(n-2) + DFS(n-1);
	}
	
	public static void main(String[] args) {
		Main2 T = new Main2();
		int n = 10;
		for(int i=1;i<=n;i++) System.out.println(T.DFS(i));
	}

}

++ 메모이제이션 사용(시간단축)

class Main2 {
	static int[] fibo;
	public int DFS(int n) {
		//이미 fibo배열에 값이 존재한다면, 탐색하지않고
		if(fibo[n]>0) return fibo[n];
        
		if(n==1) return fibo[1] = 1;
		else if(n==2) return fibo[2] = 1;
		else return fibo[n] = DFS(n-2) + DFS(n-1);
	}
	
	public static void main(String[] args) {
		Main2 T = new Main2();
		int n = 45;
		fibo = new int[n+1];
		T.DFS(n);
		for(int i=1;i<=n;i++) System.out.println(fibo[i]);
	}

}

풀이방법

첫번째 풀이는 재귀를 통해 단순히 값을 출력하는 방법이다.
하지만, 이렇게 단순히 재귀만을 하게되면 N값이 커졌을때, 모든 tree를 탐색해야하므로 시간이 오래걸린다.
예를들어, DFS(45)는 DFS(43) + DFS(44)인데 그값을 도달하기위해
또, DFS(44) = DFS(42) + DFS(43) .... 이런 과정을 쭉~ 거쳐야하므로,
비효율적이다.

DFS(N)값이 생성될때 fibo배열에 그 값을 저장하고 가져다쓰는 메모이제이션을 이용하면 시간단축을 획기적으로 할 수있다.

하지만, 재귀함수를 이용한 방법을 절대적으로 배열을 이용해 출력하는방법보다 느릴수밖에 없다.

왜냐하면, 재귀함수는 한번 재귀될 때마다 stack frame에 매개변수,지역변수,주소 등이 쌓이고 이는 배열보다는 비효율적이기 때문이다.

핵심키워드

재귀함수가 비효율적인 순간이 많기는해도, 어떻게 쓰는지, 어떻게 값이 쌓이는지 이해하자!