SICP 练习 1.16 - 我的解决方案正确吗？

Question

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 , keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product ab^n is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

所以我非常努力地想出了这个解决方案：

(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

这运行得很好，但我不确定这是否是作者要求我做的。这有什么问题吗？我的解决方案真的是迭代的吗？

Answer 1

您的解决方案不是迭代的。迭代过程是在递归调用之后不调用任何东西的过程，这两行不是这种情况：

(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 之后，没有什么可做的了，该过程只是 returns 它的值。聪明的编译器会检测到这一点，并将递归调用转换为一个循环，该循环将使用恒定数量的堆栈内存（而不是随着每次递归调用而增加。）

SICP 练习 1.16 - 我的解决方案正确吗？

SICP Exercise 1.16 - Is my solution correct?

lisp

scheme

computer-science

sicp