피보나치 수열은 0과 1로 시작해서 그 다음의 숫자는 이전 두 숫자의 합으로 이루어집니다.

피보나치 수열을 정의 하는 점화식은 다음과 같습니다.

이러한 피보나치 수열의 성질을 이용해서 손쉽게 피보나치 수열의 n번째 수를 구하는 메소드를 만들 수 있습니다.

n = 0  일 경우에는 0을 리턴

n = 1 일 경우에는 1을 리턴

그 외의 경우에는 메소드에 (n-1)과 (n-2)을 넣고 각각의 리턴값을 더한 후 리턴합니다.

결과는 제대로 나옵니다만, 정말 이대로 괜찮을까요?

결론적으로 위의 메소드는 성능면에서 매우 좋지 않습니다.

n이 커질수록 결과값을 내는 데까지 걸리는 시간이 기하급수적으로 늘게 됩니다. 

n이 4일때를 예로 들어보겠습니다.

fibonacci(4)는 fibonacci(3) + fibonacci(2)를 리턴합니다.

다시 fibonacci(3)은 fibonacci(2)+fibonacci(1)을, fibonacci(2)는 fibonacci(1)+fibonacci(0)을 각각 리턴합니다.

또 다시, fibonacci(3)의 리턴값 중 fibonacci(2)는 fibonacci(1)+fibonacci(0)을 리턴하고 

fibonacci(4)는 그제서야 결과값을 받게 됩니다.

즉 위의 피보나치 메소드의 시간복잡도(Time Complexity)는 n이 1씩 증가할 때마다 2배씩 늘어 O(2ⁿ)가 되게 됩니다.

다음은 이러한 성능 문제를 개선한 새로운 메소드입니다. 

n 이 0일 때와 1일때에는 똑같이 0과 1을 리턴해줍니다.

그리고 재귀적으로 함수를 계속 호출하는 대신 fibonacci(0)과 fibonacci(1)을 이용해 차례차례 다음 수들을 계산해 갑니다.

사실상 사람이 피보나치 수열을 계산하는 방식과 같습니다.

이렇게 함으로써 불필요한 연산들을 줄이고 효율적으로 피보나치 수열의 n항을 구할 수 있습니다.