Recursive Addition in Lisp

Question

I'm a beginner and I am trying to teach myself Common Lisp and during my self-study I have written a function that I believe should work for recursive addition of two arguments. However, the function always fails. Why is that?

(defun sum (n m)
  ;;;Returns the sum of n and m using recursion
  (cond ((eq m 0) n))
  (sum (1+ n) (1- m)))

As I understand it, it should continually add 1 to n while decrementing m until m is 0 at which point, the recursive addition is complete

You call SUM recursively. It stops when the stack overflows. Maybe you should improve the condition to stop it calling itself... Try using IF. Also EQ is not for numbers. Use EQL or =. — Rainer Joswig
– Rainer Joswig, Commented Sep 23, 2014 at 14:28
The indentation is correct according to the code. cond does something that is thrown away (n or nil) then unconditional recurse by adding n and reducing m. It won't return nil since it won't halt. You do get a stack overflow message right? — Sylwester
– Sylwester, Commented Sep 23, 2014 at 18:49
@Sylwester Yes, I get a stack overflow message in Emacs. Studying what others have corrected me on showed me how I actually messed up with my cond statement and why the recursion never ends. — BurnedOut
– BurnedOut, Commented Sep 23, 2014 at 23:55

uselpa · Accepted Answer · 2014-09-23 15:25:26Z

5

I think you have 2 simple typos:

one parenthesis too many and
missing t in your cond clause.

What you probably meant was:

(defun sum (n m)
  (cond 
   ((eq m 0) n)               ; here you had one parenthesis too many
   (t (sum (1+ n) (1- m)))))  ; here you were missing the `t` symbol

answered Sep 23, 2014 at 15:25

uselpa

19k2 gold badges36 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

BurnedOut Over a year ago

Thank you. I thought my code was just completely wrong but it is a little encouraging to see that I was 2 small typos away from having something working.

uselpa Over a year ago

@BurnedOut No you were pretty close. While I would also use if rather than cond here, some people recommend to always use cond for various reasons, such as the Racket style guide.

sigjuice · Accepted Answer · 2014-09-23 16:27:00Z

5

It's really wierd use case to do such addition, but I'll explain you where is your mistakes:

(defun sum (n m)
  ;;;Returns the sum of n and m using recursion
  (cond ((eq m 0) n)) ;; <= This line is ignored, you not returnin N.
  (sum (1+ n) (1- m))) ;; <= this will be called forever

You should write:

(defun sum (n m)
  "Recursively increment N and decrement M untill M = 0"
  (if (= m 0) ;; don't use EQ for numbers, use EQL or =.
    n
    (sum (1+ n) (1- m)))) ;; Otherwise recursive call

Let's trace it to see how it works:

CL-USER> (sum 0 10) 
  0: (SUM 0 10)
    1: (SUM 1 9)
      2: (SUM 2 8)
        3: (SUM 3 7)
          4: (SUM 4 6)
            5: (SUM 5 5)
              6: (SUM 6 4)
                7: (SUM 7 3)
                  8: (SUM 8 2)
                    9: (SUM 9 1)
                      10: (SUM 10 0)
                      10: SUM returned 10
                    9: SUM returned 10
                  8: SUM returned 10
                7: SUM returned 10
              6: SUM returned 10
            5: SUM returned 10
          4: SUM returned 10
        3: SUM returned 10
      2: SUM returned 10
    1: SUM returned 10
  0: SUM returned 10
10

If you'll take an advice - don't try to do such weird things with recursion, if you want to leard how to use it, try it for some natural-recursive cases like factorials, fibonacci, tree processing and such.

edited Sep 23, 2014 at 16:27

sigjuice

30k14 gold badges71 silver badges96 bronze badges

answered Sep 23, 2014 at 14:29

sheikh_anton

3,4722 gold badges19 silver badges24 bronze badges

6 Comments

soulcheck Over a year ago

or at least align cond test forms to each other. The error could easily be spotted if cond wasn't on the same level as recursive call to sum.

sheikh_anton Over a year ago

Of course he can use cond, but if you have onli two branches if is idiomatic.

soulcheck Over a year ago

Yes, clearly if would be more idiomatic here. Just mentioning cond in case OP gets into similar problems in some other case, where cond would be idiomatic.

BurnedOut Over a year ago

Thank you. I think I'm understanding Lisp a lot better and can see why my code was failing. And I'll certainly take your advice and stick to more naturally recursive problems :)

galdre Over a year ago

The OP's use-case is a standard text-book example of using recursion to build up primitive operations in university computability courses.

|

Collectives™ on Stack Overflow

Recursive Addition in Lisp

2 Answers 2

2 Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related