트리 프로세스는 같은 작은 문제를 되풀이한다.
단순한 피보나치 재귀는 서로 겹치는 호출로 갈라지므로 작은 답을 얻는 데도 되풀이되는 일이 빠르게 늘지만 반복 상태 프로세스는 인덱스마다 한 번씩 진행합니다.
같은 피보나치 값을 돌려주는 두 프로시저의 시간과 공간 요구량은 어떻게 다르게 자랄까요?
- 서로 겹치는 부분 문제가 있는 호출 트리 알아보기
- 돌려준 값과 재귀 적용 횟수를 따로 세기
- 남아 있는 프로세스 상태로 최대 재귀 깊이 따라가기
- 빠르게 자라는 트리 작업과 선형 반복 단계 비교하기
- 유한한 측정값과 모든 구현에 대한 증명을 구분하기
직접 작성한 fib 프로시저는 n이 2 이상일 때마다 더 작은 호출 두 개를 만듭니다. 두 갈래는 서로 겹칩니다. fib 3은 fib 5의 양쪽 갈래 안에서 다시 나타나고 그 아래에서도 같은 일이 반복됩니다. 반환된 수에는 이렇게 되풀이된 이력이 남지 않으므로 호출 수와 최대 깊이를 따로 세어 프로세스의 모양을 드러냅니다.
n이 8이면 계측한 트리는 67번의 프로시저 적용 뒤 21을 반환하고 깊이 8에 닿습니다. 반복 프로세스는 이웃한 피보나치 값 두 개와 남은 횟수만 가지고 같은 값에 여덟 단계 만에 닿습니다. 이 교과서적인 두 프로시저에서 단순 재귀의 시간은 지수적으로 자라고 깊이는 선형으로 자라며 반복 프로세스의 시간은 선형이고 상태 변수 수는 일정합니다. 화면의 숫자는 여전히 이 유한한 프로그램과 입력만 설명합니다.
(begin
(define calls 0)
(define maximum-depth 0)
(define (record-call! depth)
(set! calls (+ calls 1))
(set! maximum-depth (max maximum-depth depth)))
(define (fib n depth)
(record-call! depth)
(if (< n 2)
n
(+ (fib (- n 1) (+ depth 1))
(fib (- n 2) (+ depth 1)))))
(let ((value (fib 8 1)))
(list value calls maximum-depth)))- 출력
- —
- 값
- —
- 진단
- —
첫 프로그램은 (21 67 8)을 반환합니다. 두 번째 프로그램은 ((4 3 9 4) (5 5 15 5) (6 8 25 6) (7 13 41 7))을 반환합니다.
각 적용이 n 빼기 1과 n 빼기 2로 갈라지는 곳을 찾고 같은 작은 n의 호출이 되풀이되는지 살펴보세요. 빠르게 늘어나는 calls 필드와 요청한 인덱스마다 정확히 하나씩 늘어나는 반복 steps 필드를 비교하세요. 이벤트 한도에 닿으면 평가가 끝나기 전에 제한된 실행 흐름의 기록만 먼저 멈출 수 있습니다.
힌트를 보기 전에 프로그램을 바꿔 보세요.
n이 9일 때 값과 재귀 호출 수와 최대 깊이를 예상한 뒤 반복 단계 수와 비교하고 프로그램을 바꿔 실행하세요.
힌트 하나 보기
재귀 호출 수는 9, 15, 25, 41, 67, 109로 이어지며 반복 프로세스는 n번 전이합니다.