Поскольку нет никакого априорного ограничения на число вложенных рекурсивных вызовов, нам может понадобиться хранить произвольное число значений регистров. Значения эти требуется восстанавливать в порядке, обратном порядку их сохранения, поскольку в гнезде рекурсий последняя начатая подзадача должна завершаться первой. Поэтому требуется использовать для сохранения значений регистров стек (stack), или структуру данных вида «последним вошел, первым вышел». Можно расширить язык регистровых машин и добавить в него стек, если ввести два новых вида команд: значения заносятся на стек командой save и снимаются со стека при помощи команды restore. После того, как последовательность значений сохранена на стеке, последовательность команд restore восстановит их в обратном порядке.3

С помощью стека можно использовать для всех подзадач-факториалов единую копию путей данных факториальной машины. Имеется подобная проблема и при использовании последовательности команд контроллера, который управляет путями данных. Чтобы запустить новое вычисление факториала, контроллер не может просто перейти в начало последовательности, как в итеративном процессе, поскольку после решения подзадачи поиска (n - 1)! машине требуется еще домножить результат на n. Контроллер должен остановить вычисление n!, решить подзадачу поиска (n - 1)! и затем продолжить вычисление n!. Такой взгляд на вычисление факториала приводит к использованию механизма подпрограмм из раздела 5.1.3, при котором контроллер с помощью регистра continue переходит к той части последовательности команд, которая решает подзадачу, а затем продолжает с того места, где он остановился в главной задаче. Мы можем таким образом написать факториальную подпрограмму, которая возвращается к точке входа, сохраненной в регистре continue. При каждом вызове подпрограммы мы сохраняем и восстанавливаем регистр continue подобно регистру n, поскольку все «уровни» вычисления факториала используют один и тот же регистр continue. Так что факториальная подпрограмма должна записать в continue новое значение, когда она вызывает сама себя для решения подзадачи, но для возврата в место, откуда она была вызвана для решения подзадачи, ей потребуется старое значение continue.

На рисунке 5.11 показаны пути данных и контроллер машины, реализующей рекурсивную процедуру factorial. В этой машине имеются стек и три регистра с именами n, val и continue. Чтобы упростить диаграмму путей данных, мы не стали давать имена кнопкам присваивания регистров, и поименовали только кнопки работы со стеком - sc и sn для сохранения регистров, rc и rn для их восстановления. В начале работы мы кладем в регистр n число, факториал которого желаем вычислить, и запускаем машину. Когда машина достигает состояния fact-done, вычисление закончено и результат находится в регистре val. В последовательности команд контроллера n и continue сохраняются перед каждым рекурсивным вызовом и восстанавливаются при возврате из этого вызова. Возврат из вызова происходит путем перехода к месту, хранящемуся в continue. В начале работы машины continue получает такое значение, что последний возврат переходит в fact-done. Регистр val, где хранится результат вычисления факториала, не сохраняется перед рекур-

решим подзадачу, можно эту единицу добавить и восстановить старое значение. Такая стратегия работает для факториала, но в общем случае она работать не может, поскольку старое значение регистра не всегда можно вычислить на основании нового.

3В разделе 5.3 мы увидим, как стек можно реализовать на основе более элементарных операций.

сивным вызовом, поскольку после возврата из подпрограммы его старое содержимое не нужно. Используется только новое значение val, то есть результат подвычисления.

Несмотря на то, что в принципе вычисление факториала требует бесконечной машины, машина на рисунке 5.11 конечна, за исключением стека, который потенциально неограничен. Однако любая конкретная физическая реализация стека будет иметь конечный размер и таким образом будет ограничивать возможную глубину рекурсивных вызовов, которые машина сможет делать. Такая реализация факториала иллюстрирует общую стратегию реализации рекурсивных алгоритмов в виде обыкновенных регистровых машин, дополненных стеком. Когда нам требуется решить рекурсивную подзадачу, мы сохраняем на стеке регистры, текущее значение которых потребуется после решения этой подзадачи, решаем ее, затем восстанавливаем сохраненные регистры и продолжаем выполнение главной задачи. Регистр continue следует сохранять всегда. Нужно ли сохранять другие регистры, зависит от конкретной машины, поскольку не все рекурсивные вычисления нуждаются в исходных значениях регистров во время решения подзадачи (см. упражнение 5.4).

Двойная рекурсия

Рассмотрим более сложный рекурсивный процесс - древовидную рекурсию при вычислении чисел Фибоначчи, описанную в разделе 1.2.2:

(define (fib n)

(if (< n 2)

n

(+ (fib (- n 1)) (fib (- n 2)))))

Как и в случае с факториалом, рекурсивное вычисление чисел Фибоначчи можно реализовать в виде регистровой машины с регистрами n, val и continue. Машина более сложна, чем факториальная, поскольку в последовательности команд контроллера здесь два места, где нам нужно произвести рекурсивный вызов - один раз для вычисления Fib(n-1), а другой для вычисления Fib(n-2). При подготовке к этим вызовам мы сохраняем регистры, чье значение нам потребуется позже, устанавливаем в регистр n число, Fib от которого нам требуется вычислить (n - 1 или n - 2), и присваиваем регистру continue точку входа в главной последовательности, куда нужно вернуться (соответственно, afterfib-n-1 или afterfib-n-2). Затем мы переходим к метке fib-loop. При возврате из рекурсивного вызова ответ содержится в val. На рисунке 5.12 показана последовательность команд контроллера для этой машины.

(controller

(assign continue (label fact-done)) ; установить адрес

; окончательного возврата fact-loop

(test (op =) (reg n) (const 1)) (branch (label base-case))

;; Подготовиться к рекурсивному вызову, сохраняя n и continue.

;; Установить continue так, что вычисление продолжится

;; с after-fact после возврата из подпрограммы. (save continue) (save n)

(assign n (op -) (reg n) (const 1)) (assign continue (label after-fact)) (goto (label fact-loop)) after-fact (restore n) (restore continue)

(assign val (op *) (reg n) (reg val)) ; теперь val содержит n(n - 1)! (goto (reg continue)); возврат в вызывающую программу

base-case

(assign val (const 1)); базовый случай: 1! = 1

(goto (reg continue)); возврат в вызывающую программу

fact-done)

Рис. 5.11: Рекурсивная факториальная машина.