[인프런] Javascript - 재귀의 기초2 (점화식, 피보나치수열, 다이나믹 프로그래밍 memoization)

* 이 글은 인프런에서 제공하는 호눅스님의 유료 강의 '쉽고 자연스럽게 배워보는 Javascript 입문 - 코드스쿼드 마스터즈 코스 레벨1'를 듣고 공부하며 정리한 글입니다. 강의 내용에 더해, 제가 필기하고 구글링한 내용이 정리되어 있습니다. 초보인 제가 이해한 대로 정리했기 때문에, 부정확한 내용이 있을 수 있음을 감안해 주시길 바랍니다. 강의를 듣고 내용을 정리한 글이기 때문에 문제가 되지 않는다는 인프런 측 답변을 받은 적이 있으나(https://bibi6666667.tistory.com/37), 저작권상 문제가 된다면 보호 모드(비공개)로 전환하겠습니다.

 

점화식

재귀나 다이나믹 프로그래밍이라는 걸로 문제를 풀 때 유용하게 사용할 수 있는 수학 공식입니다.

(구글링) 점화식 (= 재귀식, recurrence relation)
: (수학)수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다.

---

 

재귀로 피보나치 수열 구현하기

피보나치 수열이란 오래 된 수학 문제 중 하나입니다. 무인도 토끼 문제로도 알려져 있습니다.

참고 : 피보나치 수열

m.blog.naver.com/PostView.nhn?blogId=brain_m&logNo=221100195745&proxyReferer=https:%2F%2Fwww.google.com%2F

[신기한 수열 이야기]피보나치수열/레오나르도피보나치/토끼수열/자연속피보나치수열

 

※ 아기 토끼는 다 자라는 데 한 달이 걸리며, 다 자란 토끼는 아기 토끼를 한 쌍 낳는다.
토끼는 늙지 않고 영원히 아기 토끼를 낳을 수 있다.

어떤 무인도에 아기 토끼가 한 쌍 들어온다.
한 달 뒤) 어른 토끼 한 쌍이 아기 토끼 한 쌍을 낳는다.
두 달 뒤) 어른 토끼 두 쌍이 각각 아기 토끼 한 쌍을 낳는다.

.. n개월 뒤에 토끼는 총 몇 쌍이 있을까?

 

피보나치 수열의 점화식

f(0) = 0,  > 처음 : 0쌍.
f(1) = 1,  > 첫째 달 : (아기토끼) 1쌍
f(2) = f(1) + f(0)= 1 + 0 = 1 > 둘째 달 : 어른토끼 1쌍
f(3) = f(2) + f(1) = 1 + 1 = 2 > 셋째 달 : 어른토끼 1쌍, (아기토끼) 1쌍 = 2쌍
f(4) = f(3) + f(2) = 2 + 1 = 3 > 넷째 달 : 어른토끼 2쌍, (아기토끼) 1쌍 = 3쌍
f(5) = f(4) + f(3) = 3 + 2 = 5 > 다섯째 달 : 어른토끼 3쌍, (아기토끼) 2쌍 = 5쌍
...
정리하면
f(0) = 0  > 처음 : 0쌍
f(1) = 1  > 첫째 달 : (아기토끼) 1쌍
...
f(n) = f(n-1) + f(n-2)  > n째 달 = n-1번째 달의 토끼 수 + n-2번째 달의 토끼 수

 

---

 

재귀로 피보나치 수열을 구현하기

첫 번째 방법

 var fibo = function (n) { // n개뭘 후 토끼 쌍의 수.
        if (n == 0) { //n이 0이면 0.
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fibo(n - 1) + fibo(n - 2);
        }
    }
    fibo(0); // 0
    fibo(1); // 1
    fibo(2); // 1
    fibo(3); // 2
    fibo(4); // 3
    fibo(5); // 5
    fibo(6); // 8

 

그러나 위 코드의 치명적 문제는..
: 매번 함수를 호출해 같은 계산을 반복한다 (이미 계산해서 아는 값인데도).
( = 함수를 불필요하게 너무 많이 호출한다)
왜? 컴퓨터는 '이미 알고 있는 값이라는 사실 자체를 모르기 때문에' 필요할 때마다 똑같은 계산을 또 하는 것.

fibo(40); 만 해 보아도 결과 출력이 조금씩 느려짐을 알 수 있다.
(fibo(40)을 위해 컴퓨터는 몇억 번도 넘게 계산을 해야 하기 떄문)

예를 들어 fibo(10) 이라고 해 보면..
fibo(10) = fibo(9) + fibo(8)
1. fibo(9)를 구하기 위해 fibo(9) = fibo(8) + fibo(7), 
->fibo(8)을 구하기 위해 fibo(8) = fibo(7) + fibo(6)을 구하고
->fibo(7)을 구하기 위해 fibo(7) = fibo(6) + fibo(5)를 구한다.
구했던 값을 대입하는 게 아닌 매번 새로 계산.
2. fibo(8)을 구하기 위해 fibo(8) = fibo(7) + fibo(6),
->fibo(7)을 구하기 위해 fibo(7) = fibo(6) + fibo(5)를 구한다.
->fibo(6)을 구하기 위해 fibo(6) = fibo(5) + fibo(4)를 구한다.
역시 구했던 값을 대입하는 게 아닌 매번 새로 계산.

 

대안 : 두 번째 방법 (옵션)

var arr =[0, 1]; 

function fibo_d(n) {
    if(arr[n] == undefined) {
        arr[n] = fibo_d(n - 1) + fibo_d(n - 2);
    }
    return arr[n];
} 

이런 방법을 다이나믹 프로그래밍(또는 memoization메모이제이션) 기법이라고 합니다.
-> 코드 설명은 생략. 지금은 그냥 이런 개념이 있다는 것만 알고 넘어가기. (어차피 지금 수준에서 설명 불가능..)
(같은 결과를 훨씬 더 빠르게 출력해 주는 알고리즘의 묘미이다)