<보기>는 피보나치 수열을 계산하는 C 프로그램이다. fib… | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 26년 1회차
<보기>는 피보나치 수열을 계산하는 C 프로그램이다. fib(5)을 호출했을 때, 함수 fib( )가 호출되는 총 횟수는? (단, 첫 호출도 1회로 계산한다.)int fib(int n)
{
if(n==0) return 0;
if(n==1) return 1;
return (fib(n-1) + fib(n-2));
}
1
7
2
12
3
15
4
17
해설
fib(5)를 호출하면 함수는 총 15회 호출된다.
호출 횟수를 이라 하면 , 이다.
- 7회: 중복 호출을 대부분 빠뜨린 값이다.
- 12회: 재귀 트리의 일부 호출을 누락한 값이다.
- 17회: 실제보다 많이 센 값으로, n이 0 또는 1이면 더 재귀하지 않는다는 점과 맞지 않는다.
오류나 개정된 내용이 보이면 알려주세요