Search code examples
schemerackettail-recursionhtdp

Can this be turned into a tail recursive function?

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.

Solution

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