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

Question

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

(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:

Упражнение 1.16: Разработка процедуры, которая эволюционирует итерационный процесс возведения в степень, которая использует последовательную квадратуру и использует логарифмическое число шагов, как это делает фаст-эксп. (Подсказка: используя наблюдение, что (b (^ n/2))^2 = (b (^ 2))^n/2 , держите вместе с показателем n и базой b дополнительное состояние переменную a и определить преобразование состояния таким образом, чтобы произведение ab^n не менялось из состояния в состояние. В начале процесса a принимается равным 1, а ответ задается значением a в конец процесса. В общем, метод определения инвариантной величины, который остается неизменным из состояния в состояние, является мощным способом думать об дизайне итеративных алгоритмов.)

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

(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))) 

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

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

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

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

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

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

Answer 1

Вот несколько иной реализация для создания вещи яснее, обратите внимание, что я использую процедуру помощника под названием 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, IMHO 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))))))