recursion - 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
> 

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

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

Answer 1

您的代码中显示的过程是递归的 - 您可以看到在每次调用时，在 else 部分中仍有一个操作仍在等待:加法。通常，迭代过程将答案作为参数(累加器)传递，递归调用位于尾位置——也就是说，它是最后一件事我们这样做了，没有任何待处理的操作。

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

(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