recursion - 使用递归乘以方案

每当第二个数字（在这种情况下为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))))))

最佳答案

如果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))

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