가상 계산기는 첫 두 값 F₀=0, F₁=1을 알고 있어요. 그다음 값은 바로 앞의 두 값을 더해 만들어요. 여섯 번째 값 F₆을 구할 때, 중간값을 기억하는지에 따라 덧셈 횟수도 같을까요? 값은 단위 없는 수이며 덧셈 한 번만 한 회로 세어요.
중간 결과를 버리는 방식은 F₆을 구하려고 F₅와 F₄를 각각 처음부터 계산해요. F₅ 안에도 F₄ 계산이 들어가므로 같은 일을 반복해요. Aₙ을 이 방식의 덧셈 횟수라 하면, 이미 아는 두 값에서는 A₀=A₁=0입니다.
A₂부터 A₆까지는 1, 2, 4, 7, 12입니다. 두 하위 계산을 마친 뒤 더하는 한 회를 빠뜨리면 안 돼요. 최종 값은 8이지만 그 값을 얻는 데 덧셈 12회가 필요해요.
반면 F₂=1, F₃=2, F₄=3, F₅=5, F₆=8을 순서대로 만들고 저장하면 새 값마다 덧셈 한 회만 해요. n=2부터 6까지 다섯 단계이므로 5회예요. 이전 두 값만 보관해도 다음 값을 만들 수 있어요. 같은 정의와 같은 답을 사용해도 중간 결과를 다시 계산하느냐가 작업량을 바꿔요. 여기서는 덧셈 횟수만 비교하며 실제 기기의 저장 비용과 실행 시간은 따로 측정해야 해요.
참고한 수학 개념: AMS · Primitive Recursion and the Disappearing Guests.
이 글의 생활 상황과 계산 예시는 수학 이야기에서 새로 구성했습니다.