1 
(define (even x)  (= (modulo x 2) 0))
(define (twice x) (* x 2))
(define (half x)  (/ x 2))  

(define (rfmult a b)
    (cond ((= 0 a) 0)
          ((= 0 b) 0)
          ((even a) (twice (rfmult (half a) b)))
          (else     (+ b (twice (rfmult (half (- a 1)) b))))))

我已经理解(rfmult 3 4)被称为，该else语句被触发，然后(- 3 1)发生a并被切成两半，所以它变成了(rfmult 1 4)。在这一点上，我迷路了，因为如果它乘以 2，它就永远不会结束。我只是在我的脑海中似乎无法理解它。

4

2 回答 2

2

递归在“基本情况”（没有递归调用）处结束。您的基本情况是a或是。b0

使用“跟踪定义”

|(rfmult 3 4)
| (rfmult 1 4)
| |(rfmult 0 4)       ;; ends here
| |0
| 4
|12

像这样：

(trace-define (rfmult a b)    ; <= here
    (cond ((= 0 a) 0)
          ((= 0 b) 0)
          ((even a) (twice (rfmult (half a) b)))
          (else     (+ b (twice (rfmult (half (- a 1))b))))))
于 2013-09-29T02:37:59.223 回答
1

我想我想通了......所以让我们打电话（rfmult 100 5）

  1. 这将调用 (rfmult (100/2 5)
  2. (50/2 5)*2
  3. ((25-1)/2 5) *2
  4. (12/2 5) * 2 + b
  5. (6 5)*2
  6. (3 5)*2
  7. ((3-1)/2 5) *2
  8. (1 5)*2 + b
  9. 0！

然后你通过递归向上跟踪。

因此，在 (1 5) 块中，b 值变为 15，因为 5*2 + 5=15

然后，(3 15) 块 b 变为 15 *2 = 30

然后，(6 30) b 变为 30 * 2 = 60

那么，(12 60) 60*2 + 5 = 125

(25 125) 125 * 2 => 250

这让我们回到 (50 250) 的第一次调用，其中 250*2 = 500，这就是 5*100 的解决方案......

如果这是错误的思考过程，请纠正我！我已经坐在这个递归结构上大约 2 个小时了，很高兴看到它有点道理！

于 2013-09-28T20:59:02.463 回答