Упражнение SICP 1.16 - Правильно ли мое решение? - PullRequest
Новая
       82

Упражнение SICP 1.16 - Правильно ли мое решение?

2 голосов
/ 29 сентября 2019

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

Так что я очень старался и пришелс этим решением: 

(define (exp b n)
  (exp-iter b n 1))

(define (square p) (* p p))

(define (even? k)
  (= (remainder k 2) 0))

(define (exp-iter b counter product)
  (define (smash counter)
    (if (even? counter) (square (exp-iter b (/ 2 counter) product)) (* b (exp-iter b (- counter 1) product))))
  (if (= counter 0) product (smash counter)))

(exp 4 3) ;test

Это работает отлично, но я не уверен, что это то, что автор попросил меня сделать. Есть ли проблемы с этим? Мое решение действительно итеративное?

1 Ответ

1 голос
/ 30 сентября 2019

Ваше решение не является итеративным. Итеративная процедура - это та, которая ничего не вызывает после рекурсивного вызова, и это не так в следующих двух строках: 

(square (exp-iter b (/ 2 counter) product))
(* b (exp-iter b (- counter 1) product))

После вызова exp-iter в первой строке вы передаетерезультат до square, а во второй строке вы умножаете результат на b. Сравните это с хвостовым рекурсивным решением: 

(define (exp-iter b counter product)
  (cond ((= counter 0)
         product)
        ((even? counter)
         (exp-iter (square b) (/ counter 2) product))
        (else
         (exp-iter b (- counter 1) (* b product)))))

Обратите внимание, что после вызова exp-iter ничего не остается, и процедура просто возвращает свое значение. Умный компилятор обнаружит это и преобразует рекурсивный вызов в цикл, который будет использовать постоянный объем стековой памяти (вместо увеличения при каждом рекурсивном вызове.)

...