스택은 돌아온 뒤 해야 할 일을 기억한다.
명시적인 스택은 재귀 팩토리얼 프로세스가 호출 속에 남겨 둘 곱셈을 직접 저장할 수 있습니다.
생각해 볼 질문
기계가 재귀 문제 안으로 내려가는 동안 무엇을 저장해야 할까요?
- Move pending multiplication onto an explicit stack
- Use a phase register to distinguish descent from return
- Connect stack depth with suspended work
During descend, the machine pushes n and continues with n minus one. At the base case it places 1 in value and switches the phase to return.
During return, each transition pops one saved multiplier and updates value. An empty stack means no suspended multiplication remains, so value is the final answer.
(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))리스펙스 학습용 런타임리스펙스 SICP 프로필 1.0.0
리스펙스 SICP 런타임 불러오는 중
리스펙스 · SICP 코드UTF-8 428 / 1,048,576바이트
예제
결과—
- 출력
- —
- 값
- —
- 진단
- —
보이는 실행 흐름0 / 0 개의 실행 이벤트
The first program returns (120 9). The machine performs five descent transitions and four stack pops.
Find the point where phase changes from descend to return. Before it, stack grows by cons. After it, stack shrinks by cdr as value grows.
힌트를 보기 전에 프로그램을 바꿔 보세요.
Run the machine for 6 and predict both the factorial value and the number of transitions.
힌트 하나 보기
There are n descent transitions and n minus one return transitions.