# 피보나치 수
## 문제
피보나치 수는 아래의 조건을 만족한다.
+ n > 1 인 경우, F(n) = F(n -1) + F(n - 2)
+ n = 1 인 경우, F(1) = 1
+ n = 0 인 경우, F(0) = 0
예를 들면 아래와 같다.
```
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
...
F(n) = F(n - 1) + F(n - 2)
```
주어진 뼈대코드는 피보나치 수를 만드는 두 메소드를 비교한다. recursive 구현과 iterative구현의 차이를 입력란을 통해 설명하시오.
## 뼈대코드
```
public class Fibonacci {
public static void main(String[] args) {
for (int i = 0; i <= 20; i++) {
printComparingFibonacci(i);
}
}
public static void printComparingFibonacci(int n) {
// variables
long start = 0;
long end = 0;
int result = 0;
// recursive
start = System.nanoTime();
result = recursiveFib(n);
end = System.nanoTime();
System.out.printf("재귀 F(%2d) = %4d in %7dns || ", n, result, end - start);
// iterative
start = System.nanoTime();
result = iterativeFib(n);
end = System.nanoTime();
System.out.printf("연속 F(%2d) = %4d in %7dns\n", n, result, end - start);
}
public static int recursiveFib(int n) {
if (n <= 1) {
return n;
}
return recursiveFib(n - 1) + recursiveFib(n - 2);
}
public static int iterativeFib(int n) {
if (n <= 2) {
if (n == 2) {
n -= 1;
}
return n;
}
int fn = 0;
int prev1 = 1;
int prev2 = 1;
for (int i = 3; i <= n; i++) {
fn = prev1 + prev2;
prev2 = prev1;
prev1 = fn;
}
return fn;
}
}
```
## 입력 예
```
recursion 구현이 더 코드가 짧네요.
짧으면 좋은 코드 아닌가요?
```