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

피보나치 수열의 총 항을 입력받아 피보나치 수열을 출력한다.

 

예를들어 5를 입력 받으면 1, 1, 2, 3, 5를 출력한다.

 

재귀함수를 사용해 구현을 할 계획인데 우선 재귀의 기본 형태부터 구현하여 원리를 이해해 본다.

public static void main(String[] args) {
	
	System.out.println(DFS(5));
}
	
public static int DFS(int n) {
		
	if(n == 1) return 1;
	else if(n == 2) return 1; 
	else return DFS(n - 2) + DFS(n - 1);
}

우선 위 코드는 피보나치 수열의 n번째 항을 구하기 위해 이전전항(n-2)와 이전항(n-1)의 항을 재귀하며 값을 구하고 최종 합산하여 결과를 출력한다.

 

대략적인 재귀 흐름을 다음과 같다.

때문에 n번째 항까지의 전체 피보나치 수열을 출력하기 위해선 단순하지만 for문을 돌려 DFS(n)을 계산해 주면 된다.

for(int i = 1 ; i <= 5; i++) {
	System.out.print(DFS(i) + " ");
}

 

다만, n 이 증가하게 된다면 아래와 같이 불필요한 반복 작업이 수없이 많이 진행되기 때문에 개선이 필요하다.

첫번째 개선 방법은 예를들어 n = 6일 때 1부터 6까지 계속 DFS()를 호출하는게 아니라 결국 DFS(6) 만 호출하면 내부 과정중에 DFS(1)부터 DFS(6)까지의 과정이 모두 포함되어 있다는점을 이용하는 방법이다.

 

public class Test {

	static int[] cache;
	
	public static void main(String[] args) {

		int n = 6;
		
		// 0번째 index는 무시하기 위해 n+1로 생성
		cache = new int[n+1];
		
		// DFS()는 한번만 호출한다.
		DFS(n);
		
		for(int i = 1 ; i <= n; i++) {
			System.out.print(cache[i] + " ");
		}
		
	}
	
	public static int DFS(int n) {
		
		if(n == 1) return cache[n] = 1;
		else if(n == 2) return cache[n] = 1; 
		else return cache[n] = DFS(n - 2) + DFS(n - 1);
	}
}

중요한 부분은 DFS()는 n 값으로 한번만 수행을 하며 내부 수행 과정중에 cache라는 전역 배열에 값을 사전에 바인딩 후 나중에 for문을 돌려 배열에 저장된 값을 출력하는 부분이다.

 

다만, 이 부분도 불필요한 과정이 포함되어 있다.

 

위 재귀 흐름을 보면 DFS(6)을 돌때도 DFS(4), DFS(3) 등의 호출이 반복되고 있는데 만약 n이 40 정도로 증가하게 된다면 반복 작업은 훨씬 더 많이 지게 된다.

 

이를 방지하기 위해 메모이제이션 방식을 사용하여 cache 배열에 저장된 값이 있다면 더 이상 계산하지 않고 해당 값을 바로 활용하도록 코드를 추가한다.

public class Test {

	static int[] cache;
	
	public static void main(String[] args) {

		int n = 6;
		
		// 0번째 index는 무시하기 위해 n+1로 생성
		cache = new int[n+1];
		
		// DFS()는 한번만 호출한다.
		DFS(n);
		
		for(int i = 1 ; i <= n; i++) {
			System.out.print(cache[i] + " ");
		}
		
	}
	
	public static int DFS(int n) {
    
		// 메모이제이션  추가
		if(cache[n] > 0) return cache[n];
        
		if(n == 1) return cache[n] = 1;
		else if(n == 2) return cache[n] = 1; 
		else return cache[n] = DFS(n - 2) + DFS(n - 1);
	}
}

 

추가된 코드는 if(cache[n] > 0) return cache[n];  한줄이다.

초기 배열이 0으로 초기화 되어 있기 때문에 초기화되지 않았다면(값이 이미 계산되어 저장되어 있다면) 더 이상 계산하지 않고 해당 값을 바로 return 시켜줌으로서 불필요한 계산을 최소화 할 수 있다.