보통의 대부분의 사람이 그렇듯이(나 역시 낑낑대면서 푼 결과가 아래이다.) 처음 피보나치를 풀면 아래와 같이 풀이하게 된다.
public class No01 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for (int i = 1; i <= n; i++) {
System.out.println(dfsN(n));
}
}
public static int dfsN(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 1;
} else {
return dfsN(n - 2) + dfsN(n - 1);
}
}
}
n=45쯤을 넣게 되면 엄청난 시간이 소요된다. 다음값을 나올때까지 꽤나 오래 기다려야 한다.
그래서 이것을 좀 더 개선해보면 아래와 같이 배열에 재귀함수의 결과를 기록하는 것이다.
public class No01 {
public static int[] fibo;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
fibo = new int[n + 1];
dfsN(n);
for (int i = 1; i <= n; i++) {
System.out.println(fibo[i]);
}
}
public static int dfsN(int n) {
if (n == 1) {
return fibo[n] = 1;
} else if (n == 2) {
return fibo[n] = 1;
} else {
return fibo[n] = dfsN(n - 2) + dfsN(n - 1);
}
}
}
한 차원 더 업그레이드하여 메모이제이션을 쓰면 시간을 더욱 단축할 수 있다. 말하자면 fibo배열에 저장해놓은 값을 쓰는 것이다. 메모이제이션을 쓰고 실행해보면 결과가 바로 출력된다.
public class No01 {
public static int[] fibo;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
fibo = new int[n + 1];
dfsN(n);
for (int i = 1; i <= n; i++) {
System.out.println(fibo[i]);
}
}
public static int dfsN(int n) {
if (fibo[n] != 0) {
return fibo[n];
}
if (n == 1) {
return fibo[n] = 1;
} else if (n == 2) {
return fibo[n] = 1;
} else {
return fibo[n] = dfsN(n - 2) + dfsN(n - 1);
}
}
}
재귀와 반복문의 성능을 비교하면 당연히 반복문의 성능이 우월하다. 그 이유는 반복문의 경우 스택프레임을 하나만 쓰는데, 재귀의 경우 재귀로 호출할 때마다 스택프레임을 계속해서 쓰기 때문이다.