피보나치 수열

[재귀] 피보나치 수열

재귀문제로 피보나치 수열을 접한 사람은 어마어마하게 많을 것이다. 그러나, 피보나치 수열을 재귀적으로 이해하지 못하는 사람이 너무나도 많음을 느낀다. 피보나치 수열은 어렵다. 이 문제를 쉬운 문제라고 말하는 것은 옳지 못하다고 생각한다. 다만 쉽게 풀어서 설명해보고자 한다. 피보나치 수열 피보나치 수열이란 뭘까? 피보나치라는 사람이 발견한 수열이며, 수열로써 특정 식을 가지고 쭉 뻗어 나간다. 피보나치 수열은 아래의 점화식으로 표현이 가능하다. F0 = 0, F1 = 1, F(n + 2) = F(n + 1) + Fn 그러나 여기에서는 굳이 점화식이라는 단어를 써가며 재귀함수를 공부하지 말자. 위를 직관적으로 표현하면 아래와 같다. 15번째 항까지 나열된 피보나치 수열을 보자. 1, 1, 2, 3, 5, ..