Linear Peano multiplication in Scheme?

Question

I've been running through The Little Schemer, and have hit the example of Peano multiplication. The solution is given in TLS (reproduced below) -- however what interests me is the order of the algorithm.

(define mX
  (lambda (n m)
    (cond
      ((zero? m) 0)
      (else
        (+ n (mX n (1- m))))
      )))

My understanding is that this sort of operation is to be avoided, as the order of the operation is unnecessarily large.

To that end I've been trying to think of how to convert this to a linear operation (I was able to do so in the case of addition). Nesting two functions occurred to me, but once i do this i am unsure how to measure the order of the function.

(define (mX n m)
  (define (mX-aux n m product)
    (if (zero? m)
      product
      (mX-aux n (1- m) (+ product n))))
  (mX-aux n m 0))

Is this approach linear or recursive? Is there a another way to do this? In particular, is it possible to do this without setting variables?

Answer 1

Let's look at a simpler problem first: counting the length of a list. Here's the recursive way to do it:

(define (length lst)
  (if (null? lst)
      0
      (+ 1 (length (cdr lst)))))

Okay, so, what would it look like if instead of recursing, we kept a running count of the length instead?

(define (length lst)
  (length-aux lst 0))

(define (length-aux lst count)
  (if (null? lst)
      count
      (length-aux (cdr lst) (+ 1 count))))

Here, length-aux tail-recurses into itself over and over with a new running count until we hit the end of the list, at which point we return the count.

This idiom is common enough that Scheme has a concept called named let, which you can use like this:

(define (length lst)
  (let loop ((lst lst)
             (count 0))
    (if (null? lst)
        count
        (loop (cdr lst) (+ 1 count)))))

You can use a similar approach for solving your problem iteratively:

(define (mX n m)
  (let loop ((m m)
             (product 0))
    (if (zero? m)
        product
        (loop (- m 1) (+ product n)))))

Notice that we are not setting variables here. We are doing a tail recursion into loop, which is passed the new m and product values as arguments.