将递归过程转换为迭代过程 - 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:

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 (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 更新： 去年，我完全忘记了这个练习和我见过的解决方案。我尝试解决它，最终我使用练习中提供的不变量作为转换状态变量的基础自行解决了它。我使用现在接受的答案来验证我的解决方案。谢谢@Óscar López。

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，恕我直言 acc 是一个更具描述性的名称）。所以一开始我们将 acc 设置为一个适当的值，然后在每次迭代中我们更新累加器，保留不变量。

一般来说，这是 "trick" 用于理解算法的迭代、尾递归实现的方法：我们传递一个额外的参数以及我们目前计算的结果，并且 return 它最终到达递归的基本情况。顺便说一句，如上所示的迭代过程的通常实现是使用一个命名的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))))))

将递归过程转换为迭代过程 - SICP 练习 1.16

Turning a recursive procedure to a iterative procedure - SICP exercise 1.16

recursion

scheme

loops

sicp

exponentiation