• 피보나치 수열은 f(n) = f(n-1) + f(n-2)를 만족하는 수열이다.
• 0번째부터 시작하여 0번째 수는 0, 1번째 수는 1이다.

재귀를 이용한 피보나치 수열 구현

• 재귀를 사용해서 피보나치 수열을 구현할 수 있다.
• 하지만 재귀를 이용하는 방법의 **시간복잡도는 O(2^n)**이기 때문에 상당히 비효율적이라고 할 수 있다.

1function fibonacci(num) {

	if(num <= 1) {
    return num;
  }

  /* recursive case
  1. f(n) = f(n-1) + f(n-2)의 형태로 리턴해준다. -> 피보나치 수열
  2. f(3) = f(2) + f(1) => f(2) = f(1) + f(0) 따라서 f(3) = f(1) + f(0) + f(1)이 되니까 f(3) = 2
  */
  return fibonacci(num-1) + fibonacci(num-2);

}

반복문을 이용한 피보나치 수열 구현

• 반복문을 사용해서 피보나치 수열을 구현할 수 있다.
• 재귀함수에 비해 간단하진 않지만 **시간복잡도는 O(n)**으로 재귀에 비해 훨씬 효율적이다.

function fibonacci(num) {
  if (num === 0) {
		return 0;
	}

  // init
  let pre = 0; // 0번째 수는 0
  let cur = 1; // 1번째 수는 1
  let fiboNum = 0; // fibonum

	// 0번째와 1번째 값을 세팅해줬기 때문에 i는 2부터 돌린다.
  for (let i = 2; i <= num; i++) {
    fiboNum = pre + cur;
    pre = cur;
    cur = fiboNum;
  }
  return fiboNum;
}

피보나치의 일반항을 이용한 피보나치 수열 구현

• 피보나치 일반항은 다음과 같다.

• 일반항을 사용하여 피보나치 수열을 구현할 수 있다.
• 일반항을 이용한 **시간복잡도는 O(logn)**이 되므로 훨씬 효율적이라고 할 수 있다.

function fibonacci(num) {

	let sqrt_5 = 5 ** (1/2);
	let ans = Math.floor(1 / sqrt_5 * (((1 + sqrt_5) / 2) ** num - ((1 - sqrt_5) / 2) ** num));
	
	return ans;
}

Dynamic Programming을 이용한 피보나치 수열 구현

• memoization을 이용하여 구하는 방법이다.
• **시간복잡도는 O(n)**이 된다.

function fibonacci(num) {
	// memoization 개념을 사용한다.
	// memo 배열을 하나 만들어준다.
	let memo = [];

	// num을 매개변수로 하는 fibo함수를 만들어준다.
	let fibo = (num) => {
		// num이 1보다 작거나 같으면 n을 리턴한다.
		if(num <= 1) {
			return n;
		} else {
				// 1보다 큰 경우에는 memo에 num이 있는지 확인한다.
				if(memo[num] !== undefined) {
					// memo에 num이 있으면 그냥 memo[num]을 리턴한다.
					return memo[num];
				} else {
						// memo에 num이 없는 경우 fibo함수를 재귀시켜준다.
						memo[num] = fibo(num-1) + fibo(num-2);
						// 재귀적으로 돌아 memo배열에 있는 값을 리턴한다.
						return memo[num];
					}
			}
	}
	// fibo(num)을 리턴해준다.
	return fibo(num);
}