LeetCode - fibonacci number

fibonacci number

• Difficulty : easy

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).

• 피보나치 수열 구현하기. N 이라는 숫자값이 주어지면 N 까지의 수열값 구하기
• N : 3 -> 0 + 1 + 1 = 2

solution

• 작성 언어 : javascript
• Runtime : 92 ms

/**
 * @param {number} N
 * @return {number}
 */
var fib = function fibonacciNumber(N) {
    
    if(N <= 1) {
        return N;
    }
        
    return fibonacciNumber(N-1) + fibonacciNumber(N-2);
        
};

• 재귀호출로 쉽게 해결이 가능하며, 함수표현식을 재귀적으로 사용하려면 이름을 부여하면된다.(기명함수표현식)
• f(N-1) + f(N-2); 를 기억하면 쉽게 해결이 가능
• 기저조건은 N <= 1 값일 때, N 을 반환해주면 된다.
• 재귀호출이므로, 이걸 무한히 호출하면 stack overflow 가 발생할 확률이 높다.

• Runtime : 64 ms

/**
 * @param {number} N
 * @return {number}
 */
var fib = function fibonacciNumber(N, before = 0, after = 1, sum = 0) {
        
    if(N === 0) return sum;
    if(N === 1) return sum ? sum : 1;
    
    sum = before + after;  
    return fibonacciNumber(N-1, before = after, after = sum, sum = sum);
};

• 꼬리재귀(tail recusion) 형태로 코드 수정