Algorithm] 피보나치(메모이제이션)

재귀 및 메모이제이션을 이용

fibo(5)를 수행한다고하면(5개의 피보나치 값 출력)

fibo(5) = fibo(4) + fibo(3);

fibo(4) = fibo(3) + fibo(2);

fibo(3) = fibo(2) + fibo(1);

를 수행하면 된다.

점화식을 구하면

fibo(n) = fibo(n-1) + fibo(n-2);

이므로 아래와 같이 재귀 함수를 구성하면 된다.

코드에서 보면 fibo의 첫 네줄동안 이상한 코드가 들어간다. static array선언과 그 array값을 return하는 코드인데 이 작업은 memoiztion에 해당한다. 

일반적으로 아무 처리없이 재귀함수를 작성하면 위의 트리와 같이 모든 함수를 재귀하며 연산한다. 그런데 이미 한번 연산했던(f3->f2->f1)과 같은 작업을 f5의 오른쪽 자식호출에서 한번 더 반복한다. 지금은 4층짜리 트리모양이라서 한 두 번 정도의 함수콜은 영향을 별로 미치지 않지만 방문 해야하는 함수가 많아질수록 기하급수적으로 연산이 늘게된다.

그래서 static array를 사용하여 방문한 장소마다 memo를 한다. 그래서 memo를 한 장소에서는 재귀적으로 함수를 call하지않고 기록한 값을 읽어와서 불필요한 중복 함수콜이 일어나지 않게 한다.

이미 방문한 곳의 값은 static array에서 갖고왔기때문에 f3에서는 별다른 함수 call이 일어나지 않는다.