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