Whenever the second number(y in this case) is a negative the code does not give me an answer and eventually crashes. So (RecursiveMultiply 9 3) works, (RecursiveMultiply -9 3) works, (RecursiveMultiply 9 -3) crashes, (RecursiveMultiply -9 -3) crashes.

This is the code I have

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

3 Answers

5
Jodast On

Your procedure goes on forever if y is negative, you can fix this by changing your if to a cond that has a condition with different code to accommodate a negative number if y is indeed negative.

The part that has the problem, (if (= y 1) x (+ x (RecursiveMultiply x(- y 1)))) Is basically saying if y is 1, return x. If y is not 1, execute the procedure again after decrementing y. Your problem is that if y is negative or zero, it is already less than 1. Subtracting 1 from a negative number/zero only pushes y further and further away from 1, and you will never actually reach 1. Your procedure is stuck in an infinite loop and crashes the interpreter.

Here's how you fix the problem:

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

I would also like to point out that your procedure is slow, it runs O(n), which means that the time/space needed to run the procedure grows linearly as the input grows, which is very bad when dealing with large numbers. I would recommend making this an iterative function instead to make it run O(log n), a much faster function.

Here is an example of an iterative multiplication procedure I wrote that runs O(n) worst case and O(log n) best case:

(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))

Try to recreate this but with your procedure.

1
simmone On

Your recursive function's end condition is "(= y 1)".

But when y is negative, it's never meet this condition, it turned to a infinite loop.

Change

(RecursiveMultiply x (- y 1)) 

to

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

Welcome to beautiful Racket lang.

0
Community On

Note #1: I am confused as to why you are using (define f (lambda(arguments) ...)) instead of using (define (f arguments) ...). You also should be using (sub1 y) instead of (- y 1). Additionally, the if should be replaced with cond, which is much cleaner.

The problem is simple, you are subtracting 1 from y when y ≠ 1, and when y is a negative number, its value will decrease indefinitely, creating an infinite loop that will ultimately crash your program.

Note #2: I have cleaned up some of your code as explained from "Note #1"

The "professional" way to solve this (taught in most schools) is to create an auxiliary function, or a function that only serves the purpose of modifying an existing function.

;; 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)]))

Examples:

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

It even works with 0!

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