5.1.4 · Сохранение отложенной работы

Стек как память о возврате

Явный стек может хранить множители, которые рекурсивный процесс вычисления факториала иначе оставил бы в отложенных вызовах.

Вопрос для размышления

Какую информацию сохраняет машина во время спуска в рекурсивную задачу?

Перенос отложенного умножения в явный стек
Использование регистра phase для различения спуска и возврата
Связывание глубины стека с отложенной работой

Во время descend машина помещает n в стек и продолжает работу с n минус один. В базовом случае она записывает 1 в value и переключает phase на return.

Во время return каждый переход извлекает один сохраненный множитель и обновляет value. Пустой стек означает, что отложенного умножения не осталось, поэтому value является окончательным ответом.

Код SICP428 из 1,048,576 байт UTF-8

(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). Машина выполняет пять переходов спуска и четыре извлечения из стека.

На что обратить внимание в трассе

Найдите точку, в которой phase меняется с descend на return. До нее стек растет за счет cons. После нее стек уменьшается за счет cdr по мере роста value.

Попробуйте сами

Измените программу и сравните результат.

Запустите машину для значения 6 и предскажите как значение факториала, так и число переходов.

Показать подсказку

Выполняется n переходов спуска и n минус один переходов возврата.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%