피보나치 문제 Javascript

피보나치 수열

0번째 피보나치수는 0이고, 1번째 피보나치 수는 1입니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, ... 증가한다.

반복문 사용하는 방법이 있지만, 시간 복잡도를 고려했을 때 재귀함수를 사용하는 것이 좋습니다.

피보나치 구하는 재귀함수

function fibo (n) {
	if(n <= 1){
    	return n;
    } else {
    	return fibo(n - 1) + fibo(n - 2);
    }
}

그럼 문제를 풀어보자.

function solution(n){
	// 피보나치의 0번째, 1번째는 고정값이다.
	let newArr = [0, 1];
    
    let getFibo = (n) => {
    	if(newArr[n] !== undefined){
        	return newArr[n];
        } else {
        	newArr[n] = getFibo(n - 1) + getFibo(n - 2);
            return newArr[n];
        }
    }
    return getFibo(n);
}

n번째 요소가 있는 경우 if(newArr[n] !== undefined)가 성립된다. 따라서 newArr[n]들어 있는 숫자를 반환하면 됩니다.

하지만 newArr[n] === undefined 라면 else 문으로 넘어가 getFibo(n - 1) + getFibo(n - 2) 값을 구해서 newArr[n] 넣어줍니다.