JAVA 피보나치 수열 (배열 vs 재귀 함수 )

이번글에서는 피보나치 수열을 배열 방식과 재귀함수 방식 두 개를 비교해보려고 한다. 

 

피보나치 수열은 간단하게 설명하자면,

1 1 2 3 [5] 8 ...   [5]의 값이 나오려면 앞에 두자리 2 와 3을 더하면 되는 구조이다.

-> 간단하게 말해 어떤 수열의 항이 그 앞의 두 항의 합과 같은 수열을 말한다!

 

그럼 아래 예시를 통해 배열과 재귀함수 두 방식의 코드를 비교해보겠다.

 

#문제 - 입력된 n만큼 피보나치 수열 출력하시오.

 

1) 배열 방식 문제 풀이

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		//입력받은 값 n
	    int n = in.nextInt();
	    
	    //피보나치수열을 담을 배열 생성
	    int[] answer = new int[n];
	    
	    //ex) 1 1 2 3 5 8 13 .....
	    answer[0] = 1; //배열 0번째는 1
	    answer[1] = 1; //배열 1번째는 1
	    
	    //for문은 배열의 2번째부터 시작
	    for(int i=2;i<n;i++) {
	    	//피보나치수열은 해당 수열의 항의 앞의 두자리 값의 합과 동일함.
	    	answer[i] = answer[i-2] + answer[i-1];
	    }
	    
	    //출력
	    for(int x : answer) {	    	
	    	System.out.print(x + " ");
	    }
	}	
}

 

- 배열은 0부터 시작이므로 arr[0]과 arr[1]에 초기값으로 각각

1을 넣어준다.

 

 

이미 arr[0]과 arr[1]에 초기값을 셋팅했으므로, arr[2]번째부터 값을 부여하기 위해 for문을 2부터 시작한다.

피보나치 수열은 해당 answer[i]는 answer배열의 앞 두항의 합과 같으므로 위와 같은 식이 성립된다.

 

answer[] 배열에 담을 값을 향상된 for문으로

출력하였다. 

 

 

10을 입력하면 위와 같은 값이 나온다.

2) 재귀함수 방식 문제 풀이 

import java.util.Scanner;

public class Main {

	static int[] answer; //static 변수 선언
	public int DFS(int n) {
		
		if(answer[n] > 0) {
			return answer[n];
		}
		
		if(n == 1) {
			return answer[n] = 1;
		}else if(n == 2) {
			return answer[n] = 1;
		}else {
			return answer[n] = DFS(n-2)+DFS(n-1);
		}
	}
	
	public static void main(String[] args) {
		Main M = new Main();	//DFS는 static 메소드가 아니므로 객체를 생성 후 사용가능
		Scanner sc = new Scanner(System.in);		
		int n = sc.nextInt();	//입력값 n
		answer = new int[n+1];	//재귀함수의 경우 배열의 순서와 입력값의 숫자를 동일하게 넣는다. 
	
		for(int i=1;i<=n;i++) {
			System.out.print(M.DFS(i) + " ");			
		}
	}
}

위의 배열 풀이와 같이 n이 1 과 2일 때 초기값으로 1을 셋팅한다. 

 

else 구문에  있는 DFS 메서드를 사용하여 피보나치 수열의 값을 구하는 재귀함수를 호출시키는데, 이를 실행할 시 Stack Frame으로 인하여 시간이 많이 걸린다. 

 

 

 

이를 보안하기 위한 방법으로 이와 같은 코드를 추가하면 속도가 빨라진다. 

 

 

 

숫자 배열을 생성하면 모든 배열의 값은 0으로 초기화 되어있는데,

DFS 메서드를 실행해서 answer[] 배열에 이미 값을 넣었으면 0보다 큰 수의 값이 들어있으면 아래 로직을 다시 실행시키지 않고 바로 값을 return 한다. 

입력값 10을 넣으면 배열문제와 동일값이 출력된다.

 

위의 두 방식에서 물론 배열의 방식이 속도가 더 빠르다. 재귀함수의 경우에 stack frame으로 값을 계속 저장하고 체크하는 방식이기 때문에 속도가 배열에 비해 오래 걸리게 된다.