[재귀] 피보나치 수열

재귀문제로 피보나치 수열을 접한 사람은 어마어마하게 많을 것이다.

그러나, 피보나치 수열을 재귀적으로 이해하지 못하는 사람이 너무나도 많음을 느낀다.

 

피보나치 수열은 어렵다.

이 문제를 쉬운 문제라고 말하는 것은 옳지 못하다고 생각한다.

 

다만 쉽게 풀어서 설명해보고자 한다.

---

피보나치 수열

피보나치 수열이란 뭘까?

피보나치라는 사람이 발견한 수열이며, 수열로써 특정 식을 가지고 쭉 뻗어 나간다.

피보나치 수열은 아래의 점화식으로 표현이 가능하다.

• F0 = 0, F1 = 1, F(n + 2) = F(n + 1) + Fn

그러나 여기에서는 굳이 점화식이라는 단어를 써가며 재귀함수를 공부하지 말자.

---

위를 직관적으로 표현하면 아래와 같다.

15번째 항까지 나열된 피보나치 수열을 보자.

• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610

피보나치 수열에서 첫번째 항과 두번째 항까지는 1이고

세번째 항부터 (n - 1) + (n - 2) 의 형태로 쭉 증가한다.

 

그렇다면 뭔가 느낌이 온다.

재귀함수에서 필수적인 조건은

• 함수가 끝나는 조건과
• 계속 달라지는 input값이다.

 

만약 피보나치 수열의 5번째 항을 재귀함수로 구현한다고 가정할 경우,

1. 두번째 항부터는 1을 리턴하고,
2. 나머지는 (n - 1) + (n - 2)의 점화식을 사용하면 어떨까?

 

아래 코드처럼 말이다.

function fibo(num) {
    if (num <= 2) return 1
    return fibo(num - 1) + fibo(num - 2)
}

console.log(fibo(5))

• 수열의 첫번째 항과 두번째 항은 1이므로, input이 2 이하로 떨어질때부터 return을 1로 한다.
• 수열의 n번째 값을 구하기 위해서 (n -1) + (n - 2) 라는 식이 필요하다.
• 피보나치 수열이라 n-1 수열도 같은 공식을 공유하므로(점화식), 해당 공식을 재귀함수로 작성해준다.

 

위의 식을 그림 처럼 설명하자면 아래와 같을 것이다.

이로써 피보나치 수열을 한번 톺아보았다.

 

재귀함수가 나오면

• 종료 조건과 재귀 함수에 들어가는 변경된 인풋 조건을 확인해라.
• 그렇다면 재귀함수에 대한 이해도를 대폭 올릴 수 있다.