[algorithm] fibonacci(n번째 피보나치 수 구하기)

문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의
  합으로 정의합니다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

인자 1 : n

• number 타입의 n (n은 0 이상의 정수)

출력

• number 타입을 리턴해야합니다.

주의사항

• 재귀함수를 이용해 구현해야 합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.

 

//문제 풀이 
// fibonacci = (n-1) + (n+2)
// 기본적으로 직전의 수와 그 전의 수를 더하면 현재의 수가 나오는 공식이 성립.
// 재귀를 사용하여 이전의 수를 구해야 하고 
// 재귀를 break 할 조건을 우선 작성해 줘야 한다.
// fibonacci 의 0번째는 0 , 1번째는 1 이기 때문에 default 값으로 정해준다.
// 그 이후 번째부터는 default 값에 추가 한다.

function fibonacci (n) {
	let defaults = [0, 1];
    let result = (n) => {
    	if(defaults[n] !== undefined){ // 재귀의 break
        	return defaults[n];
        }
        defaults[n] = result(n - 1) + result(n - 2);
        return defaults[n]; // 재귀로 추가된 default의 n번째 값
     }
     return result(n); // 재귀로 n번 result 실행
}       

 

point 

· 기본적인 fibonacci 수열의 구현 방법을 알고 있어야 함.

· 재귀의 구동방법을 이해하고 있어야 함.