Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 12
Текст из файла (страница 12)
Когда мыговорим, что процедура рекурсивна, мы имеем в виду факт синтаксиса: определение процедуры ссылается (прямо или косвенно) на саму эту процедуру. Когда же мы говорим опроцессе, что он следует, скажем, линейно рекурсивной схеме, мы говорим о развитиипроцесса, а не о синтаксисе, с помощью которого написана процедура. Может показатьсястранным, например, высказывание «рекурсивная процедура fact-iter описывает итеративный процесс». Однако процесс действительно является итеративным: его состояниеполностью описывается тремя переменными состояния, и чтобы выполнить этот процесс,интерпретатор должен хранить значение только трех переменных.Различие между процессами и процедурами может запутывать отчасти потому, чтобольшинство реализаций обычных языков (включая Аду, Паскаль и Си) построены так,что интерпретация любой рекурсивной процедуры поглощает объем памяти, линейно растущий пропорционально количеству вызовов процедуры, даже если описываемый ею процесс в принципе итеративен.
Как следствие, эти языки способны описывать итеративныепроцессы только с помощью специальных«циклических конструкций» вроде do, repeat,until, for и while. Реализация Scheme, которую мы рассмотрим в главе 5, свободнаот этого недостатка. Она будет выполнять итеративный процесс, используя фиксированный объем памяти, даже если он описывается рекурсивной процедурой. Такое свойствореализации языка называется поддержкой хвостовой рекурсии (tail recursion)∗ .
Еслиреализация языка поддерживает хвостовую рекурсию, то итерацию можно выразить спомощью обыкновенного механизма вызова функций, так что специальные циклическиеконструкции имеют смысл только как синтаксический сахар31 .30 Когда в главе 5 мы будем обсуждать реализацию процедур с помощью регистровых машин, мы увидим, чтоитеративный процесс можно реализовать «в аппаратуре» как машину, у которой есть только конечный наборрегистров и нет никакой дополнительной памяти.
Напротив, для реализации рекурсивного процесса требуетсямашина со вспомогательной структурой данных, называемойстек (stack).∗ Словарь multitran.ru дает перевод «концевая рекурсия». Наш вариант, как кажется, изящнее и сохраняет метафору, содержащуюся в англоязычном термине. — прим.
перев.31 Довольно долго считалось, что хвостовая рекурсия — особый трюк в оптимизирующих компиляторах.Ясное семантическое основание хвостовой рекурсии было найдено Карлом Хьюиттом (Hewitt 1977), которыйвыразил ее в терминах модели вычислений с помощью «передачи сообщений» (мы рассмотрим эту модель вГлава 1. Построение абстракций с помощью процедур52Упражнение 1.9.Каждая из следующих двух процедур определяет способ сложения двух положительных целыхчисел с помощью процедур inc, которая добавляет к своему аргументу 1, и dec, которая отнимаетот своего аргумента 1.(define (+ a b)(if (= a 0)b(inc (+ (dec a) b))))(define (+ a b)(if (= a 0)b(+ (dec a) (inc b))))Используя подстановочную модель, проиллюстрируйте процесс, порождаемый каждой из этих процедур, вычислив (+ 4 5).
Являются ли эти процессы итеративными или рекурсивными?Упражнение 1.10.Следующая процедура вычисляет математическую функцию, называемую функцией Аккермана.(define (A x y)(cond ((= y 0)((= x 0)((= y 1)(else (A0)(* 2 y))2)(- x 1)(A x (- y 1))))))Каковы значения следующих выражений?(A 1 10)(A 2 4)(A 3 3)Рассмотрим следующие процедуры, где A — процедура, определенная выше:(define (f n) (A 0 n))(define (g n) (A 1 n))(define (h n) (A 2 n))(define (k n) (* 5 n n))Дайте краткие математические определения функций, вычисляемых процедурами f, g и h дляположительных целых значений n.
Например, (k n) вычисляет 5n2 .главе 3). Вдохновленные этим, Джеральд Джей Сассман и Гай Льюис Стил мл. (см. Steele 1975) построилиинтерпретатор Scheme с поддержкой хвостовой рекурсии. Позднее Стил показал, что хвостовая рекурсияявляется следствием естественного способа компиляции вызовов процедур (Steele 1977). Стандарт SchemeIEEE требует, чтобы все реализации Scheme поддерживали хвостовую рекурсию.1.2. Процедуры и порождаемые ими процессы531.2.2. Древовидная рекурсияСуществует еще одна часто встречающаяся схема вычислений, называемая древовидная рекурсия (tree recursion). В качестве примера рассмотрим вычисление последовательности чисел Фибоначчи, в которой каждое число является суммой двух предыдущих:0, 1, 1, 2, 3, 5, 8, 13, 21, . .
.Общее правило для чисел Фибоначчи можно сформулировать так:если n = 0 01если n = 1Fib(n) =Fib(n − 1) + Fib(n − 2) в остальных случаяхМожно немедленно преобразовать это определение в процедуру:(define (fib n)(cond ((= n 0) 0)((= n 1) 1)(else (+ (fib (- n 1))(fib (- n 2))))))Рассмотрим схему этого вычисления. Чтобы вычислить (fib 5), мы сначала вычисляем (fib 4) и (fib 3). Чтобы вычислить (fib 4), мы вычисляем (fib 3) и(fib 2). В общем, получающийся процесс похож на дерево, как показано на рис. 1.5.Заметьте, что на каждом уровне (кроме дна) ветви разделяются надвое; это отражаеттот факт, что процедура fib при каждом вызове обращается к самой себе дважды.Эта процедура полезна как пример прототипической древовидной рекурсии, но какметод получения чисел Фибоначчи она ужасна, поскольку производит массу излишнихвычислений.
Обратите внимание на рис. 1.5: все вычисление (fib 3) — почти половинаобщей работы, — повторяется дважды. В сущности, нетрудно показать, что общее числораз, которые эта процедура вызовет (fib 1) или (fib 0) (в общем, число листьев) вточности равняется Fib(n+1). Чтобы понять, насколько это плохо, отметим, что значениеFib(n) растет экспоненциально при увеличении√ n. Более точно (см.
упражнение 1.13),Fib(n) — это целое число, ближайшее к φn / 5, где√φ = (1 + 5)/2 ≈ 1.6180то есть золотое сечение (golden ratio), которое удовлетворяет уравнениюφ2 = φ + 1Таким образом, число шагов нашего процесса растет экспоненциально при увеличенииаргумента.
С другой стороны, требования к памяти растут при увеличении аргументавсего лишь линейно, поскольку в каждой точке вычисления нам требуется запоминатьтолько те вершины, которые находятся выше нас по дереву. В общем случае число шагов,требуемых древовидно-рекурсивным процессом, будет пропорционально числу вершиндерева, а требуемый объем памяти будет пропорционален максимальной глубине дерева.Для получения чисел Фибоначчи мы можем сформулировать итеративный процесс.Идея состоит в том, чтобы использовать пару целых a и b, которым в начале даютсяГлава 1.
Построение абстракций с помощью процедур54fib 5fib 4fib 3fib 2fib 1fib 3fib 2fib 2fib 11fib 1fib 01fib 11fib 1fib 0101fib 000Рис. 1.5. Древовидно-рекурсивный процесс, порождаемый при вычислении (fib 5).1.2. Процедуры и порождаемые ими процессы55значения Fib(1) = 1 и Fib(0) = 0, и на каждом шаге применять одновременную трансформациюa← a+bb←aНетрудно показать, что после того, как мы проделаем эту трансформацию n раз, a и bбудут соответственно равны Fib(n + 1) и Fib(n).
Таким образом, мы можем итеративновычислять числа Фибоначчи при помощи процедуры(define (fib n)(fib-iter 1 0 n))(define (fib-iter a b count)(if (= count 0)b(fib-iter (+ a b) a (- count 1))))Второй метод вычисления чисел Фибоначчи представляет собой линейную итерацию.Разница в числе шагов, требуемых двумя этими методами — один пропорционален n,другой растет так же быстро, как и само Fib(n), — огромна, даже для небольшихзначений аргумента.Не нужно из этого делать вывод, что древовидно-рекурсивные процессы бесполезны.
Когда мы будем рассматривать процессы, работающие не с числами, а с иерархически структурированными данными, мы увидим, что древовидная рекурсия являетсяестественным и мощным инструментом32. Но даже при работе с числами древовиднорекурсивные процессы могут быть полезны — они помогают нам понимать и проектировать программы. Например, хотя первая процедура fib и намного менее эффективна,чем вторая, зато она проще, поскольку это немногим более, чем перевод определенияпоследовательности чисел Фибоначчи на Лисп. Чтобы сформулировать итеративный алгоритм, нам пришлось заметить, что вычисление можно перестроить в виде итерации стремя переменными состояния.Размен денегЧтобы сочинить итеративный алгоритм для чисел Фибоначчи, нужно совсем немногосмекалки.
Теперь для контраста рассмотрим следующую задачу: сколькими способамиможно разменять сумму в 1 доллар, если имеются монеты по 50, 25, 10, 5 и 1 цент?В более общем случае, можно ли написать процедуру подсчета способов размена дляпроизвольной суммы денег?У этой задачи есть простое решение в виде рекурсивной процедуры. Предположим,мы как-то упорядочили типы монет, которые у нас есть.
В таком случае верно будетследующее уравнение:Число способов разменять сумму a с помощью n типов монет равняется• числу способов разменять сумму a с помощью всех типов монет, кроме первого,плюс32 Пример этого был упомянут в разделе 1.1.3: сам интерпретатор вычисляет выражения с помощью древовидно-рекурсивного процесса.Глава 1.
Построение абстракций с помощью процедур56• число способов разменять сумму a − d с использованием всех n типов монет, гдеd — достоинство монет первого типа.Чтобы увидеть, что это именно так, заметим, что способы размена могут быть поделены на две группы: те, которые не используют первый тип монеты, и те, которыеего используют. Следовательно, общее число способов размена какой-либо суммы равночислу способов разменять эту сумму без привлечения монет первого типа плюс числоспособов размена в предположении, что мы этот тип используем.
Но последнее числоравно числу способов размена для суммы, которая остается после того, как мы один разупотребили первый тип монеты.Таким образом, мы можем рекурсивно свести задачу размена данной суммы к задаче размена меньших сумм с помощью меньшего количества типов монет. Внимательнорассмотрите это правило редукции и убедите себя, что мы можем использовать его дляописания алгоритма, если укажем следующие вырожденные случаи33 :• Если a в точности равно 0, мы считаем, что имеем 1 способ размена.• Если a меньше 0, мы считаем, что имеем 0 способов размена.• Если n равно 0, мы считаем, что имеем 0 способов размена.Это описание легко перевести в рекурсивную процедуру:(define (count-change amount)(cc amount 5))(define (cc amount kinds-of-coins)(cond ((= amount 0) 1)((or (< amount 0) (= kinds-of-coins 0)) 0)(else (+ (cc amount(- kinds-of-coins 1))(cc (- amount(first-denomination kinds-of-coins))kinds-of-coins)))))(define (first-denomination kinds-of-coins)(cond ((= kinds-of-coins 1) 1)((= kinds-of-coins 2) 5)((= kinds-of-coins 3) 10)((= kinds-of-coins 4) 25)((= kinds-of-coins 5) 50)))(Процедура first-denomination принимает в качестве входа число доступных типовмонет и возвращает достоинство первого типа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
