<보기>는 피보나치 수열을 계산하는 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회 호출된다.

호출 횟수를 T(n)T(n)이라 하면 T(n)=1+T(n−1)+T(n−2)T(n)=1+T(n-1)+T(n-2), T(0)=T(1)=1T(0)=T(1)=1이다.

T(2)=1+1+1=3T(2)=1+1+1=3
T(3)=1+3+1=5T(3)=1+3+1=5
T(4)=1+5+3=9T(4)=1+5+3=9
T(5)=1+9+5=15T(5)=1+9+5=15

  • 7회: 중복 호출을 대부분 빠뜨린 값이다.
  • 12회: 재귀 트리의 일부 호출을 누락한 값이다.
  • 17회: 실제보다 많이 센 값으로, n이 0 또는 1이면 더 재귀하지 않는다는 점과 맞지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 자료구조론] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 자료구조론 기출문제 암기장 전체 보기