59 – 재귀호출의 예(피보나치 수열)

피보나치 수열은 처음 두 항의 값은 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);
}

그리고 이 함수를 이용해 하나의 예제로 만든 것이 아래의 예제 프로그램이다.

스크린샷 2017-04-05 오전 1.45.18스크린샷 2017-04-05 오전 1.45.39

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.