Can this be turned into a tail recursive function?

Question

Going through HtDP and came across a problem which was: Design the function multiply. It consumes a natural number n and multiplies it with some arbitrary number x without using *.

This is what I came up with:

(define (multiply n x)
  (cond
    [(= x 1) n]
    [else (+ n (multiply n (- x 1)))]))

It works but I'm thinking that it is not the best solution. Since this could solved as a for-loop, based on my understanding, this should be tail-recursive.

Answer 1

The key point of tail-recursive solution: keep an invariant n * x + r = const. In this case when x is zero, r contains n * x.

(define (iter-mul n x r)
  (cond ((= x 0) r)
        (else (iter-mul n (- x 1) (+ r n))))) 

You can use it as:

(define (mul n x) (iter-mul n x 0))

Answer 2

Now that others have shown you how to make a function tail-recursive, here is an alternate version of a function to multiply two positive integers which is much faster than the one you gave. Do you see how the function works?

(define (times x y)
  (let loop ((x x) (y y) (z 0))
    (if (zero? x) z
      (loop (quotient x 2) (+ y y)
            (if (odd? x) (+ y z) z)))))

Answer 3

Probably not the most elegant, but this is at least tail recursive:

(define (acc a n x)
  (if(= x 0)
    a
    (acc (+ a n) n (- x 1))))

(define (multiply n x)
  (acc 0 n x))

Answer 4

The procedure can be easily converted into a tail-recursion by using an accumulator parameter for storing the result. The following is defined for n >= 0 and x >= 0, and I'm using a named let (loop is a tail-recursive procedure, not a looping construct) to avoid the need to explicitly define a helper procedure or adding another parameter to the procedure. Here's how to do it:

(define (multiply n x)
  (let loop ((acc 0)
             (x x))
    (cond
      [(= x 0) acc]
      [else (loop (+ n acc) (- x 1))])))

Also notice that you have a bug in your code, try running (multiply 1 0) - an infinite loop.