2019. 1. 2. 20:27ㆍ카테고리 없음
문제
피보나치 수열은 1, 1, 2, 3, 5, 8, 13, 21 ... 로 다음과 같이 정의한다.
임의의 양의 정수 n에 대하여
f(1)＝１, f(2)＝１이고, n≥３일 때,
f(n)＝f(n－1) + f(n－2)
이다.
입력받은 임의의 정수 n에 대하여 n번째 피보나치 수열의 값을 구하는 함수 f(n)이
값을 반환하기까지 호출되는 횟수를 출력하는 프로그램을 작성하시오.
핵심 아이디어
ㅡ 재귀함수 활용
ㅡ 정적(static) 변수 활용
※ 결과
ㅡ 좌측은 main 함수를 한 번씩 일일이 호출한 결과를 모아 정리한 것이고,
ㅡ 우측은 main 함수 안을 while(1)로 묶어 반복 호출한 결과이다.
<main 함수>
ㅡ int형 함수의 재귀적 활용, static 변수
1. f 함수 (... count1 함수)
ㅡ 정수형 매개변수 k 를 취하는 함수 f(int)를 선언. 함숫값을 재귀적으로 정의하고, if문을 통해 초깃값을 설정하여 완성한다.
ㅡ 함수 f 가 호출될 때마다 count1 함수가 호출되어 static int형으로 선언된 cnt1 변수가 1만큼 증가한다.
ㅡ static형의 정적 변수는 초기화하지 않으면 BSS 섹션에 저장되어 (동일한 함수 내에 선언된 자동 변수와는 달리) 함수를 재호출하더라도 초기화되지 않는 특징을 갖고 있다. 이렇게 누적이 가능한 변수의 속성 덕분에 count1 함수가 호출될 때마다 정적 변수 cnt1 을 증가시키는 것만으로도 총 호출 횟수를 측정할 수 있는 것이다.
하지만 main 함수 내부 전체를 while(1) 반복문에 넣는 경우에는 상단의 ※결과 파트에서 주황색으로 표시된 것처럼 기존의 count1 함수를 통해서는 바른 결과를 기대하기 어렵다. 이는 count1 함수 내 정적 변수 cnt1 가 함수 재호출에 따라 초기화되지 않아, 필연적으로 이전 수행 결과의 영향을 받기 때문이다.
2. count2 함수
ㅡ count1의 한계를 보완하고자 함수 count2는 매개변수 k 를 활용하여 이전 실행 결과와는 무관하게 독립적으로 f(k)의 호출 횟수를 구할 수 있도록 설계되었다.
ㅡ line 4: C언어에서의 재귀함수 구성의 특성상, 초기에 f(k)로서 함수가 호출되는 것을 고려하였다.
그러나 이는 문제의 조건을 따라 위의 f(int)와 같이 정의한 함수를 기준으로 했을 때의 결과일뿐이다. 이 결과를 피보나치 수열 내 임의의 항의 값을 알기 위해 '어떤 함수'가 호출되어야 하는 횟수로 일반화시킬 수는 없다.