프로그래밍의 기초(의사 코드 트레이스)
다음 함수 fib를 fib(10)으로 호출했을 때의 반환값은?
○integer: fib(integer: n)
integer: a ← 0, b ← 1, t
for (i from 1 to n step 1)
t ← a + b
a ← b
b ← t
endfor
return a- A34
- B55
- C89
정답과 해설 보기
정답: B. 55
반복할 때마다 (a, b)는 이웃한 피보나치 수의 쌍을 하나씩 진행합니다. (0, 1) → (1, 1) → (1, 2) → (2, 3) → (3, 5) → (5, 8) → (8, 13) → (13, 21) → (21, 34) → (34, 55) → (55, 89)로 10회 진행하므로 a = 55를 반환합니다. a는 i번째 반복 후에 i번째 피보나치 수가 됩니다. 단순한 재귀로 작성하면 같은 값을 여러 번 계산하지만, 이 작성법에서는 n회의 반복으로 끝납니다.