[피보나치 수열 재귀로 구현하기 및 최적화]

아니 피보나치 언제했다고 또 까먹었어•••

먼저 재귀로 피보나치를 구현해보자면

function fibonacci(n){
  if ( n === 0 || n === 1 ) return 1;
  
  return fibonacci(n-1) + fibonacci(n-2);
}

아조 쉽죠잉? 0과 1일 때는 1을 반환하게하고 나머지는 n-1 + n-2가 더해진 값을 리턴하면 된다.

만약에 n에 2가 들어왔다면, return문에 fibonacci(1) + fibonacci(0)이 되고,

그럼 각각 1을 리턴하니 결론적으로 2를 반환하게 될 것이다.

 

하지만 위와 같은 fibonacci는 작은 숫자에는 큰 무리 없이 작동하지만 만약 숫자가 커진다면 문제가 생기게 된다. 왜냐면 가지가 뻗어가듯 수를 계산식이 늘어나기 때문이다.

따라서 각각의 수에 대한 연산과정을 기억하게 해서, 빠르게 계산결과를 처리할 수 있게 해야한다.

function fibonacci(n){

  let newArr = [0,1];
  
  let fib = n => {
    if ( newArr[n] !== undefined ) return newArr[n];

    newArr[n] = fib(n-1) + fib(n-2);
    return newArr[n];
  }

  return fib(n);
}

먼저 메모제이션에 활용할 배열을 만들어주고, 안에서 또 함수를 정의해준다.

함수 안에서 n이 배열에 있는지를 확인하고 어떤작업을 처리해주거나, 없으면 또 다른 작업을 처리해준다.

• n이 배열에 있으면 바로 그 값을 리턴때리고
• 없으면 배열에 그 값을 저장해주는데, fib(n-1) + fib(n-2)를 불러줌으로써 저장해준다. 그리고 그 값을 반환한다.
• 마지막 fibonacci 함수가 실행되면, fib의 함수가 실행되야하니까 fib(n)을 반환해준다.