Умножение в схеме с использованием рекурсии - PullRequest
Новая
       16

Умножение в схеме с использованием рекурсии

2 голосов
/ 25 апреля 2019

Всякий раз, когда второе число (в данном случае 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))))))

Ответы [ 3 ]

5 голосов
/ 25 апреля 2019

Ваша процедура продолжается вечно, если 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))

Попробуйте воссоздать это, но с вашей процедурой.

1 голос
/ 26 апреля 2019

Конечное условие вашей рекурсивной функции - "(= y 1)".

Но когда у отрицательно, оно никогда не удовлетворяет этому условию, оно превращается в бесконечный цикл.

Изменить 

(RecursiveMultiply x (- y 1))

до 

(RecursiveMultiply x (- (abs y) 1))

Добро пожаловать в прекрасный Ракет Ланг.

0 голосов
/ 04 мая 2019

Примечание # 1: Я не понимаю, почему вы используете (define f (lambda(arguments) ...)) вместо (define (f arguments) ...). Вы также должны использовать (sub1 y) вместо (- y 1). Кроме того, if следует заменить на cond, что намного чище.

Проблема проста: вы вычитаете 1 из y, когда y ≠ 1, а когда y - отрицательное число, его значение будет бесконечно уменьшаться, создавая бесконечный цикл, который в конечном итоге приведет к краху вашей программы.

Примечание # 2 : Я убрал часть вашего кода, как описано в «Примечании № 1»

«Профессиональный» способ решить эту проблему (преподается в большинстве школ) - создать вспомогательную функцию или функцию, которая служит только для изменения существующей функции. 

;; Our auxiliary function
(define (RecursiveMultiply* x y)
(cond
  [(= y 1) x]
  [else (+ x (RecursiveMultiply x (- y 1)))]))

(define (RecursiveMultiply x y)
  (cond
    ;; Both "x" and "y" are negative, so change them both to positives
    [(and (< x 0) (< y 0)) (RecursiveMultiply* (abs x) (abs y))]
    ;; "y" is negative, so it Plugs in a legal "y" value and multiplies it by -1 to be mathematically correct
    ;; We should be using * instead of the first "RecursiveMultiply", but it is obvious that you want to do this without it
    [(< y 0) (RecursiveMultiply -1 (RecursiveMultiply* x (abs y)))]
    [else (RecursiveMultiply* x y)]))

Примеры: 

(RecursiveMultiply 9 3) ; 27
(RecursiveMultiply -9 3)  ; -27
(RecursiveMultiply 9 -3)  ; -27
(RecursiveMultiply -9 -3) ; 27

Он даже работает с 0! 

(RecursiveMultiply -11 0) ; 0
(RecursiveMultiply 0 15) ; 0
(RecursiveMultiply 0 0) ; 0
...