Algorithm problem-02

재귀함수, 시간복잡도, 메모리 관리

1. 문제

• 피보나치 수열 중 n번째 수를 리턴
• 재귀함수를 이용해 구현
• 시간 복잡도와 메모리를 고려할 것

2. 시도

• 피보나치 수열의 값을 저장해 둘 배열을 선언하고
• 기본 수열 값을 저장해두고, 찾는 값이 있을 때는 그 값을 리턴해주고
• 없을 때에는 불러낼 때마다, 계산된 값을 저장하게 만들자
• 전체 함수 자체를 재귀시켜봤더니, 콜스택 초과로 실패

3. 수도코드

function fibonacci(n) {
  // fibo값을 저장해 줄 배열을 선언하고, 선행값을 저장해준다
  let bank = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
  // 내부 함수를 구현, 뱅크값이 없다면 뱅크값을 재귀로 계산해서 저장해준다
  function fibo(n) {
    if (bank[n] === undefined) {
      bank[n] = fibo(n - 1) + fibo(n - 2)
    } return bank[n]
  }
  // 내부 함수를 리턴한다
  return fibo(n)
}
// 아래의 코드는 전체를 리턴하게끔 짜서, 콜스택을 초과하거나 스코프 오류가 생겼음
// function fibonacci(n) {
//   // TODO: 여기에 코드를 작성합니다.
//   // fibo값을 저장해줄 배열을 선언하고
//   let bank = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
//   // fibo값을 계산해줄 내부 함수를 구현한다
//   // function fibo(k) {
//   //   if (k <= 1) {return k}
//   //   return fibo(k - 1) + fibo(k - 2)
//   // }
//   // 원하는 값이 배열에 없다면, 재귀로 불러와서 값을 저장하고 그 값을 리턴
//   if (bank[n] === undefined) {
//     bank[n] = fibonacci(n - 1) + fibonacci(n - 2)
//  // bank[n] = fibo(n - 1) + fibo(n - 2)
//   }
//   // 원하는 피보값이 배열에 있으면 배열의 값을 뱉어주고
//   else {return bank[n];}
// }