有人可以解释此代码经历的递归吗？

(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，它就永远不会结束。我似乎无法理解我的头脑。有人可以解释此代码经历的递归吗？

来源

2013-09-28 LostSchemer

它是一种基于乘法分配律的算法。对于两个数字a和b，其中c是1/2 a（2c = a），那么a * b等于2c * b，但也是2 *（c * b）。而且对于任何a * b，其中d是小于a（d = a - 1）的一个，则a * b = a +（d * b）。请注意，写入的函数仅适用于整数。只需通过替代模型运行。（+ 4（*（rfmult 1 4）2）），然后（+ 4（*（+ 4）（+ 4（*（+ 4（rfmult 0 4））2））到（+ 4（*（+ 4 0））2））t0（rfmult + 4（* 4 2））至（+ 8 4）至12 – WorBlux

递归结束于'基本情况'（没有递归调用）。您的基地案件是a或b是0。

使用 '跟踪定义'

|(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-29 02:37:59 GoZoner

我想我想通了......所以让调用（rfmult 100 5）

这将随后致电（rfmult（100/2 5）
（50/2 5 ）* 2
（（25-1）/ 2 5）* 2
（12/2 5）* 2 + b
（6 5）* 2
（3 5）* 2
（（3-1）/ 2 5）* 2
（1 5）* 2 + b
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 an d即5 * 100的解决方案...

如果这是错误的思维过程，请纠正我！我一直坐在这个递归结构上约2小时，很高兴看到它有意义！

来源

2013-09-28 20:59:02 LostSchemer

有人可以解释此代码经历的递归吗？

回答

相关问题