5.1.4 · 미뤄 둔 일 저장하기

스택은 돌아온 뒤 해야 할 일을 기억한다.

명시적인 스택은 재귀 팩토리얼 프로세스가 호출 속에 남겨 둘 곱셈을 직접 저장할 수 있습니다.

생각해 볼 질문

기계가 재귀 문제 안으로 내려가는 동안 무엇을 저장해야 할까요?

미뤄 둔 곱셈을 명시적인 스택으로 옮기기
phase 레지스터를 사용해 하강과 복귀 구분하기
스택 깊이를 미뤄 둔 일과 연결하기

descend 동안 기계는 n을 push하고 n - 1로 계속 진행합니다. base case에서는 value에 1을 넣고 phase를 return으로 바꿉니다.

return 동안 각 전이는 저장된 곱할 값 하나를 pop하고 value를 갱신합니다. 빈 스택은 미뤄 둔 곱셈이 더는 남아 있지 않음을 뜻하므로 value가 최종 답이 됩니다.

SICP 코드UTF-8 428 / 1,048,576바이트

(begin
  (define (run n stack value phase steps)
    (cond ((eq? phase 'descend)
           (if (= n 1)
               (run n stack 1 'return (+ steps 1))
               (run (- n 1) (cons n stack) value
                    'descend (+ steps 1))))
          ((null? stack) (list value steps))
          (else
           (run n (cdr stack) (* (car stack) value)
                'return (+ steps 1)))))
  (run 5 '() 0 'descend 0))

예제

결과—

출력: —
값: —
진단: —

실행 추적0 / 0 개 이벤트

예상 결과

첫 프로그램은 (120 9)를 반환합니다. 기계는 하강 전이 다섯 번과 스택 pop 네 번을 수행합니다.

실행 추적에서 볼 점

phase가 descend에서 return으로 바뀌는 지점을 찾으세요. 그전에는 cons로 stack이 늘어납니다. 그 뒤에는 value가 커짐에 따라 cdr로 stack이 줄어듭니다.

직접 해보기

프로그램을 수정하고 결과를 비교해 보세요.

6으로 기계를 실행하고 팩토리얼 값과 전이 횟수를 모두 예상하세요.

힌트 보기

하강 전이는 n번이고 복귀 전이는 n - 1번입니다.

이 수업 완료하기

이 장의 총 23개 수업 중 0개 완료0%