순환(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회에 두 하위 호출의 횟수가 더해진다:
- 25회: f(6)을 처음 호출했을 때의 총 호출 횟수이다.
- 35회: f(6)과 f(5) 호출분(25+15)만 더해도 40회이므로 너무 작다.
- 51회: 40회에 f(7) 자신 1회를 더한 값보다 크므로 성립하지 않는다.
오류나 개정된 내용이 보이면 알려주세요