SICP

Question

我正在使用 SICP 这本书，我正在为递归与迭代过程的概念而苦苦挣扎。在问题 1.17 中，他们这样问：

练习 1.17。本节中的取幂算法基于通过重复乘法执行取幂。类似地，可以通过重复加法来进行整数乘法。下面的乘法过程（假定我们的语言只能加，不能乘）类似于 expt 过程：

(define (* a b)
  (if (= b 0)
  0
  (+ a (* a (- b 1)))))

该算法采用的步骤数在 b 中是线性的。现在假设我们包括加法运算 double，它将一个整数加倍，和 halve，它将一个（偶数）整数除以 2。使用这些，设计一个类似于 fast-expt 的乘法过程，它使用对数步数。

（来源：https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4）

我做了以下代码，看起来是对的：

(define (* a b)
  (cond ((= b 1) a)
        ((even? b) (* (double a) (halve b)))
        (else (+ a (* (double a) (halve (- b 1)))))))

如果使用跟踪，Dr. Racket 中的调试内置函数，输入 343 和 799 我得到：

(require racket/trace)
(trace *)
(* 343 799)

>(* 343 799)
> (* 686 399)
> >(* 1372 199)
> > (* 2744 99)
> > >(* 5488 49)
> > > (* 10976 24)
> > > (* 21952 12)
> > > (* 43904 6)
> > > (* 87808 3)
> > > >(* 175616 1)
< < < <175616
< < < 263424
< < <268912
< < 271656
< <273028
< 273714
<274057
274057
>

我很困惑。我创建的过程具有递归定义，但它似乎具有递归性质和迭代性质。我错了吗？一个过程可以迭代和递归吗？

我在调试时看到树设计的递归性质。我看到了迭代性质，因为我使用 variable/parameter "a" 作为状态变量。我是不是误会了什么？

Answer 1

您的代码中显示的过程是递归的 - 您可以看到在每次调用时，在 else 部分中仍有一个操作尚未完成：加法。通常，迭代过程将答案作为参数（累加器）传递，递归调用位于 tail 位置 - 即是的，这是我们做的最后一件事，没有任何待处理的操作。

在您的堆栈跟踪中，很明显递归过程正在发生，对 * 过程的调用堆积到某个点，然后开始返回 - 它看起来像一个三角形。与此相比，真正的迭代乘法；这里我们看不到运行 trace 时的三角形，并且程序以 space:

的恒定量运行

(define (mul a b)
  (define (iter count acc)
    (if (zero? count)
        acc
        (iter (- count 1) (+ acc a))))
  (iter b 0))

(trace mul)
(mul 343 799)

>(mul 343 799)
<274057
274057

SICP - 递归或迭代过程？

SICP - Recursive or iterative process?

lisp

iteration

recursion

racket