순환(recursive) 함수 f()에 대한 첫 번째 호출이 f(7)일… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 14년 1회차
순환(recursive) 함수 f()에 대한 첫 번째 호출이 f(7)일 때, f(7)을 포함하여 함수 f()가 호출되는 총 횟수는?
int f(int n)
{
if (n == 0 || n == 1)
return n;
return f(n-1) + f(n-2);
}
1
25
2
35
3
41
4
51
해설

f(7)을 포함한 총 호출 횟수는 41회이다.

호출 횟수를 C(n)이라 하면 n이 0·1이면 자기 자신 1회이고, 그 외에는 자신 1회에 두 하위 호출의 횟수가 더해진다: C(n)=C(n−1)+C(n−2)+1C(n)=C(n-1)+C(n-2)+1

C(0)=C(1)=1C(0)=C(1)=1
C(2)=3, C(3)=5, C(4)=9C(2)=3,\ C(3)=5,\ C(4)=9
C(5)=15, C(6)=25, C(7)=25+15+1=41C(5)=15,\ C(6)=25,\ C(7)=25+15+1=41

  • 25회: f(6)을 처음 호출했을 때의 총 호출 횟수이다.
  • 35회: f(6)과 f(5) 호출분(25+15)만 더해도 40회이므로 너무 작다.
  • 51회: 40회에 f(7) 자신 1회를 더한 값보다 크므로 성립하지 않는다.

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

이어서 풀어보기

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