피보나치 수열

피보나치 수열

나는 f(n) = f(n)-f(n-1) 의 공식만 알면 다 풀었다고 생각했지만!!
재귀함수 호출과 메모이제이션 기법을 몰랐기 때문에 상당히 비효율적으로 코드작성을 했었다.(사실 많이 창피하다 기초라고하는데 기초도 몰라서..)

일반적인 피보나치 수열이지만 상당히 비효율 적인 부분이 있다.
f(5) = f(4) + f(3) 이고 ,f(4) = f(3) + f(2), f(3) = f(2) + f(1) 라고 한다면 f(5)를 구하기 위해 이미 알고 있는 값을 다시 재귀 호출하여 불필요한 자원을 소모 한다는 것을 알 수 있다.
아래와 같이 테이블의 값을 0으로 초기화 한후 메모이제이션 기법을 활용하면 해결 된다.