Превращение рекурсивной процедуры в итеративную — упражнение SICP 1.16

В книге «Структура и интерпретация компьютерных программ» описана рекурсивная процедура вычисления показателей с использованием последовательного возведения в квадрат.

(define (fast-expt b n)
    (cond ((= n 0) 
        1)
    ((even? n) 
        (square (fast-expt b (/ n 2))))
   (else 
        (* b (fast-expt b (- n 1))))))

Теперь в упражнении 1.16:

Exercise 1.16: Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does `fast-expt`. (Hint: Using the observation that 
(b(^n/2))^2 = (b(^2))^n/2

, сохраните вместе с показателем степени n и основанием b дополнительную переменную состояния a и определите преобразование состояния таким образом, чтобы произведение ab^n не менялось от состояния к состоянию. В начале процесса a принимается равным 1, а ответ дается значением a в конце процесса. В общем, метод определения инвариантной величины, которая остается неизменной от состояния к состоянию, является мощным способом подумать о разработке итерационных алгоритмов.)

Я потратил неделю и абсолютно не могу понять, как сделать эту итеративную процедуру, поэтому я сдался и стал искать решения. Все решения, которые я нашел, это:

(define (fast-expt a b n)
    (cond ((= n 0) 
        a)
    ((even? n) 
        (fast-expt a (square b) (/ n 2)))
   (else 
        (fast-expt (* a b) b (- n 1)))))

Теперь я могу понять

        (fast-expt a (square b) (/ n 2)))

используя подсказку из книги, но мой мозг взорвался, когда n нечетное. В рекурсивной процедуре я понял, почему

        (* b (fast-expt b (- n 1))))))

работает. Но в итеративной процедуре все становится совершенно иначе,

        (fast-expt (* a b) b (- n 1)))))

Он работает отлично, но я совершенно не понимаю, как самому прийти к этому решению. это кажется очень умным.

Может кто-нибудь объяснить, почему итеративное решение такое? И каков общий способ решения этих типов проблем?

Обновление 2021 г. В прошлом году я совершенно забыл об этом упражнении и решениях, которые видел. Я попытался решить ее и, наконец, решил самостоятельно, используя инвариант, представленный в упражнении, в качестве основы для преобразования переменных состояния. Я использовал принятый ответ, чтобы проверить свое решение. Спасибо, @Оскар Лопес.


loops recursion exponentiation scheme sicp
person lightning_missile    schedule 22.11.2015    source источник
comment
лол, я потратил 30 минут и расстроился. Надо обладать поразительной настойчивостью, раз потратили на это неделю.   -  person qiu    schedule 26.06.2021
comment
@qiu это зависит. В среднем я тратил от недели до месяца на решение упражнения из этой книги. Например, я потратил почти 7 месяцев на решение упражнения 1.11. Я мирился с этим, потому что почти всегда узнавал что-то после их решения. То долгое время, которое я им отдал, в конечном итоге всегда того стоит. Это исключение, потому что я на самом деле очень легко отвлекаюсь и расстраиваюсь, если нахожу что-то скучным.   -  person lightning_missile    schedule 27.06.2021

Ответы (1)


arrow_upward
3
arrow_downward

Вот немного другая реализация для большей ясности, обратите внимание, что я использую вспомогательную процедуру под названием loop для сохранения арности исходной процедуры:

(define (fast-expt b n)
  (define (loop b n acc)
    (cond ((zero? n) acc)
          ((even? n) (loop (* b b) (/ n 2) acc))
          (else (loop b (- n 1) (* b acc)))))
  (loop b n 1))

Что здесь acc? это параметр, который используется как накопитель для результатов (в книге этот параметр называется a, ИМХО acc - более описательное имя). Итак, вначале мы устанавливаем acc в соответствующее значение, а затем на каждой итерации обновляем аккумулятор, сохраняя инвариант.

В общем, это «уловка» для понимания итеративной, хвостовой рекурсивной реализации алгоритма: мы передаем дополнительный параметр с результатом, который мы вычислили до сих пор, и возвращаем его в конце, когда мы достигаем базового случая. рекурсии. Кстати, обычная реализация итерационной процедуры, показанной выше, заключается в использовании именованного let, это полностью эквивалентно и немного проще в написании:

(define (fast-expt b n)
  (let loop ((b b) (n n) (acc 1))
    (cond ((zero? n) acc)
          ((even? n) (loop (* b b) (/ n 2) acc))
          (else (loop b (- n 1) (* b acc))))))
person Óscar López    schedule 22.11.2015
comment
хорошо, я понимаю неизменную часть. Но с точки зрения решений я думал, что логика итерационных и рекурсивных процедур эквивалентна друг другу. Две реализации этой проблемы, похоже, не имеют одинаковой логики. Я прав? - person lightning_missile; 22.11.2015
comment
На самом деле они используют точно ту же логику. Оба решения заканчиваются умножением значения на b, которое не меняется. В рекурсивной версии мы умножаем b на результат рекурсивного вызова, тогда как в итеративной версии результат рекурсивного вызова накапливается в параметре, но это все равно - мы просто избегаем ожидания возврата рекурсии , передав его результат в параметре. Подумайте о том, что вы делаете, когда изменяете локальную переменную в цикле for императивного языка, здесь то же самое, мы просто используем параметры, как если бы мы использовали локальную переменную. - person Óscar López; 22.11.2015
comment
Я до сих пор не понимаю, если n нечетно. В рекурсивной версии, если n нечетно, мы делаем b * еще один вызов функции с n-1, теперь n четно. Я думаю, что b* нужно добавить еще одну базу. Например, если n равно 9, мы делаем 2* fastExp 9-8, а затем продолжаем вызовы, если n четно. Я думаю, что 2 * есть для того, чтобы девятое 2 умножалось. Но я не вижу b* в итеративной версии. Я действительно смущен тем, что происходит, если n нечетно. - person lightning_missile; 22.11.2015
comment
Это та же идея, те же шаги, тот же алгоритм, единственное, что меняется, — это то, как мы распространяем решение. В рекурсивной версии мы делаем (* b (fast-expt …)), и решение распространяется, когда мы возвращаемся в стек вызовов функций. В итеративной версии мы делаем (* b acc), потому что мы сохранили в acc результат предыдущего вызова (fast-expt …), и решение распространяется в параметре без затрат на возврат в стеке вызовов функций. - person Óscar López; 22.11.2015
comment
Рассмотрим более простой пример. Рекурсивная процедура сложения всех целых чисел между 0 и заданным числом: (define (addFirst i) (if (zero? i) 0 (+ i (addFirst (- i 1))))). Теперь та же процедура, но итеративно: (define (addFirst i a) (if (zero? i) a (addFirst (- i 1) (+ i a)))) Видите, как выполняется та же операция? просто в итеративной версии решение аккумулируется в параметре a, который должен быть инициализирован с 0 - точно такое же значение, которое вернула бы рекурсивная процедура в своем базовом случае! - person Óscar López; 22.11.2015
comment
Я получил ваш пример. Я знаю, как другая переменная отслеживает обновленные значения в итерационных процедурах. К сожалению, я не могу применить его к решению экспоненты, если n нечетно. Я знаю, почему мы делаем (* b acc) с точки зрения помещения значений в аккумулятор, я думаю, что мое замешательство связано с тем, что в рекурсивной процедуре значение b не меняется при каждом вызове. Но для итеративной процедуры b сильно меняется при возведении в квадрат. Не могли бы вы привести еще один пример, который ведет себя так? - person lightning_missile; 23.11.2015
comment
@ Оскар, когда n es даже я считаю, что было бы лучше возвести в квадрат аккумулятор. хелперу не нужен b в качестве аргумента, он не должен меняться. - person Rptx; 23.11.2015
comment
@Rptx Я не думаю, что это сработает ;) напишите доказательство концепции, протестируйте его и докажите, что я не прав :P - person Óscar López; 23.11.2015
comment
@ Оскар Лопес в рекурсивной процедуре я заметил, что b не меняется. Я могу понять, почему fastExp b n-1 умножается на основание (*b(fastexp)). Где в итерационной процедуре происходит шаг умножения исходной базы? Я знаю, что это есть в параметре a, но я не могу понять это. - person lightning_missile; 23.11.2015
comment
@morbidCode В рекурсивной процедуре b не изменяется, изменяется все значение, возвращаемое функцией, поскольку оно умножается на b. Слушай, я больше не могу тебе помочь. Возьмите лист бумаги и ручку, используйте модель подстановки и поймите, что на самом деле делает каждый процесс. - person Óscar López; 23.11.2015
comment
@ Оскар Лопес Я пытался решить эту проблему в прошлом году и, наконец, решил ее самостоятельно, используя инвариант, предоставленный в упражнении, в качестве основы для преобразования переменных состояния. Я наконец понял, что вы имели в виду. Для меня это сводится к следующему: как мне сохранить инвариант? Оглядываясь назад, я считаю, что не очень хорошо понимаю рекурсию 5 лет назад. Спасибо за этот информативный ответ! - person lightning_missile; 27.06.2021