recursion - 使用递归在 Scheme 中相乘

Question

每当第二个数字(在本例中为 y)为负数时，代码不会给我答案并最终崩溃。所以 (RecursiveMultiply 9 3) 有效，(RecursiveMultiply -9 3) 有效，(RecursiveMultiply 9 -3) 崩溃，(RecursiveMultiply -9 -3) 崩溃。

这是我的代码

(define RecursiveMultiply 
  (lambda (x y) 
    (if (= y 1) 
        x
        (+ x (RecursiveMultiply x (- y 1))))))

Answer 1

如果 y 为负数，您的过程将永远持续下去，您可以通过将 if 更改为具有不同代码条件以容纳负数的 cond 来解决此问题如果 y 确实是负数。

有问题的部分，(if (= y 1) x (+ x (RecursiveMultiply x(- y 1)))) 基本上是说 如果 y 是 1，返回 x。如果 y 不为 1，则在递减 y 后再次执行该过程。 你的问题是，如果 y 为负数或零，则它已经小于 1。从负数/零中减去 1 只会将 y 推得越来越远远离 1，你永远不会真正达到 1。你的过程陷入无限循环并使解释器崩溃。

解决问题的方法如下:

(define RecursiveMultiply 
    (lambda(x y)
        (cond ((= y 1) x)
              ((= y 0) 0)
              ((< y 1) (* -1 (RecursiveMultiply x (- y))))
              (else (+ x (RecursiveMultiply x (- y 1)))))))

我还想指出你的程序很慢，它运行 O(n)，这意味着运行该程序所需的时间/空间随着输入的增长而线性增长，这在处理大数据时非常糟糕数字。我建议使它成为一个迭代函数，而不是让它运行 O(log n)，这是一个更快的函数。

这是我编写的迭代乘法过程的示例，它运行 O(n) 最坏情况和 O(log n) 最佳情况:

(define (mult a b c)
  (define (double x)
    (* x 2))
  (define (halve x)
    (/ x 2))
  (cond ((= b 0) c)
        ((even? b)
          (mult (double a)(halve b) c))
        (else  
          (mult a (- b 1) (+ c a)))))
(define (two-number-mult x y)
    (mult x y 1))

尝试使用您的程序重新创建它。