피보나치 수열[ Fibonacci Sequence ] 이탈리아 수학자 피보나치(Fibonacci)가 발견한 피보나치 수열은 토끼 번식 이야기에서 출발한다. 어떤 남자가 벽으로 둘러싸인 장소에 한 쌍의 토끼들을 둔다. 만약 각 쌍이 두 번째 달부터 매달 토끼를 한 쌍씩 낳는다고 가정한다면 그 해에 얼마나 많은 쌍의 토끼가 생산되겠는가? 이 결과로서 생기는 수열은 다음과 같다. 1, 1, 2, 3, 5, 8, 13, 21, ··· 이 수열은 그 결실이 많다고 판명되었고, 수학과 과학의 많은 분야에서 적용되고 있다. 이 수열을 ‘피보나치 수열’이라 하고, 이 수열에서 나타나는 수들을 ‘피보나치 수’라고 한다.
피보나치 수열을 생성하는 기본 규칙은 처음 두 항은 1이고, 세 번째 항부터는 바로 앞의 두 항의 합이 된다는 것이다. 그래서 세 번째 항은 첫 번째 항 1과 두 번째 항 1을 더한 값인 2가 된다. 그리고 네 번째 항은 두 번째 항 1과 세 번째 항 2를 더한 값인 3이 된다. 피보나치 수열을 수학 공식으로 나타내면 다음과 같다. f(n) = 1 (n＜=2 일 때)
f(n) = f(n-2)+f(n-1) (n＞2 일 때) 이를 C언어 함수로 표현하면 다음과 같은데, 6행에서 재귀 호출을 수행한다. 
|
