[javascript] 피보나치 (Fibonacci)

피보나치 수열

0, 1, 1, 2, 3, 5, 8, 13, 21.... 피보나치는 0번째는 0, 첫 번째는 1 그 이후로는 이전 두개의 수를 더한 값을 갖는 수열이다.

F(0) = 0, F(1) = 1, F(n) = F(n-2) + F(n-1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


let fib = (num) => {
    if(num <= 1) return num;
    return fib(num-1) + fib(num-2);
}

console.log(fib(1))
console.log(fib(2))
console.log(fib(3))
console.log(fib(4))
console.log(fib(5))
console.log(fib(6))

재귀함수로 구현하면 간단하지만, 같은 계산을 여러번 진행하기 때문에 좋지는 않다.

그래서 반복문으로 변경할 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


let fib = (num) => {
    if(num <= 1) return num;
    let current = 1;
    let last = 0;
    for(let i = 2; i <= num; i++) {
           let tmp = current;
           current = current + last;
           last = tmp;
    }
    return current;
}

console.log(fib(1))
console.log(fib(2))
console.log(fib(3))
console.log(fib(4))
console.log(fib(5))
console.log(fib(6))

피보나치 수열

Related Posts