반복문을 이용해 해결할 수 없습니다.
피보나치 수가 처음 언급된 문헌은 기원전 5세기 인도의 수학자 핑갈라가 쓴 책이다.
한편 유럽에서 피보나치 수를 처음 연구한 것은 레오나르도 피보나치로 토끼 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다.
1000보다 작은 피보나치 수는
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
이다.
꽃씨의 배열이나 나무가지의 갈라짐 등등으로 빈번하게 등장하고, 실제 생물의 번식을 설명하는 데에도 쓰인다.
황금비의 자기닮음성이나 프랙탈에도 사용된다.
피보나치 수를 구할 때 일반적인 점화식을 가지고 프로그래밍언어로 구현할 수 있다.
이때 점화식을 통해 재귀적은 관계를 정의할 수 있다.
n번째 피보나치 수를 계산해 보자