As a Lisp (and functional programming) newbie, I wrote the following code that finds the sum of all the multiples of 3 or 5 below 1000, and I suspect that it is lousy:

(defun multiple-of-3-or-5 (x) 
    (or (eq (mod x 3) 0) (eq (mod x 5) 0)) )

(defun generate-list (min max) 
    (cond ((> min max) nil) 
          (t (cons min (generate-list (+ min 1) max )))))

(defun my-sum (my-list) 
    (cond ((atom my-list) 0) 
          (t (+ (cond ((multiple-of-3-or-5 (car my-list)) (car my-list)) 
              (t 0)) 
            (my-sum (cdr my-list))))))

Any general advice is most welcome. Specifically, I have these questions (other than what you could say):

  1. I had to extend the stack multiple times (using LispWorks) to get a result. Is my use of recursion wrong?
  2. Should I prefer iterative approach over recursion in Lisp too? (as in imperative languages)
  3. Should I use the loop macro if I am to solve it in iterative fashion?

4 Answers 4


Is my use of recursion wrong?

It's not wrong, but it's unnecessarily complex. There's no need to create a list and recurse over it when you could simply iterate over the numbers.

Should I prefer iterative approach over recursion in Lisp too? (as in imperative languages)

Iteration is perfectly acceptable in functional languages! Functional programmers talk about recursion a lot, because it's more flexible (and thus more powerful) than iteration, but we use iteration too, when we don't need that power. This is why most functional languages have plenty of iteration tools built in — Common Lisp's mapcar, some, reduce, loop and do, for example.

Use iteration when it's the simplest solution, and recursion when you need it.

Should I use the loop macro if I am to solve it in iterative fashion?

Sure, loop is the simplest way to do this, so it's what most Common Lispers would do. It's a bit complex for beginners, though; do might be easier to learn.

Comments on the implementation

generate-list is traditionally called range or iota. Rather than define it yourself, you can get it from a library such as Alexandria.

The explicit recursion in my-sum is not necessary. It's simpler (and clearer) to use the standard sequence functions remove-if-not and reduce instead:

(reduce #'+ (remove-if-not #'multiple-of-3-or-5 (iota 1000)))

The best way to test for the end of a list is endp, not atom. (It also signals an error on improper lists.)

(1+ min) is a little clearer than (+ min 1).

  1. You are not using tail recursion in my-sum, so the compiler cannot easily turn it into iteration.

  2. It depends on the specific problem; in this case I would probably do it iteratively.

  3. Sure, loop is useful and convenient.

Here is my attempt:

(defun multiple-of-3-or-5 (x) 
    (or (zerop (mod x 3))
        (zerop (mod x 5))))
(defun my-sum (from to)
  (loop :for i :from from :to to
    :when (multiple-of-3-or-5 i) 
    :sum i))
  • \$\begingroup\$ Or without loop: (let ((sum from)) (dotimes (i to) (when (multiple-of-3-or-5 i) (setq sum (+ sum i)))) sum) \$\endgroup\$
    – Drew
    Commented May 19, 2014 at 2:00
  • 2
    \$\begingroup\$ @Drew: (incf sum i) \$\endgroup\$
    – Anonymous
    Commented May 19, 2014 at 4:22
  • \$\begingroup\$ @Anonymous: Yes, of course. Been using older Emacs-Lisp versions too long. \$\endgroup\$
    – Drew
    Commented May 19, 2014 at 4:26

I agree with sds's post. In addition, you should note that eq does not guarantee to return true for two equal numbers (see, especially, the (let ((x 5)) (eq x x)) case). You should use zerop to test if a number is zero (and = for comparing numeric equality in general).

  • 1
    \$\begingroup\$ That would take me long to discover, thanks! \$\endgroup\$
    – henginy
    Commented May 19, 2014 at 7:38
  • \$\begingroup\$ But if they're both numbers of the same type, then eql is OK. \$\endgroup\$ Commented Jun 22, 2014 at 19:21

You're solving the problem inefficiently; in the same way that you can mentally figure out in a few seconds that the sum of every number from 1 to 100 inclusive is 5050, you can do the same here:

999/5 = 199 instances, divided by 2 is 99 (plus 500, the half-way mark)

5 + 995 = 1000 sum of opposite numbers

1000 sum * 99 instances = 99,000

999/3 = 333 instances, divided by 2 is 166 (plus 501, the half-way mark)

3 + 999 = 1002 sum of opposite numbers

1002 sum * 166 instances = 166,332

And now to allow for where 3 and 5 are double counted:

999/5*3 = 66 instances, divided by 2 is 33

15 + 990 = 1005 sum of opposite numbers

1005 sum * 33 instances = 33,165

Answer = 99,000+500 + 166,332+501 - 33,165

This algorithm doesn't scale well beyond a handful of numbers, but works very well for large ranges.

  • 2
    \$\begingroup\$ You are correct in pointing out that this is a problem that can be solved analytically, but does the calculation you offer consider the fact that every 15th integer is a multiple of both 3 and 5? \$\endgroup\$ Commented May 19, 2014 at 4:30
  • \$\begingroup\$ Well spotted. Fixed. \$\endgroup\$
    – Josh
    Commented May 19, 2014 at 6:06
  • 2
    \$\begingroup\$ Thanks for the improvement in the algorithm but my focus is really on the code itself. \$\endgroup\$
    – henginy
    Commented May 19, 2014 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.