피보나치 수열은 처음 두 항의 값은 1이지만, 그 다음 항부터는 이전의 두 항의 합이 된다. 즉, 세 번째 항은 첫 항과 두 번째 항인 1을 더한 2가 되고, 네 번째 항은 두 번째 항과 세 번째 항을 합한 3이 된다. 이걸 그대로 쭉 적으면 다음과 같이 된다.
1 1 2 3 5 8 13 21 ……
즉, 처음 두 항을 제외한 나머지 항들에서 n항의 값은 n-1 항과 n-2 항을 더한 것이다. 피보나치 수열의 항에 따라 수식을 정리하면 다음과 같이 도니다.
- fibo(n)
- 1, n = 1
- 1, n = 2
- fibo(n-1) + fibo(n-2), n > 2
C 함수로 나타내면 다음과 같이 작성할 수 있을 것이다. 종료 조건이 n은 1이거나 2일 때 1을 반환하도록 작성하면 된다.
int fibo(int n)
{
if(n==1 || n==2)
return 1;
else
return fibo(n-1) + fibo(n-2);
}
그리고 이 함수를 이용해 하나의 예제로 만든 것이 아래의 예제 프로그램이다.