CODEWITHSUNDEEP
recursionlispcommon-lisptail-recursion
Too Legit To Not Program
Too Legit To Not Program

Reputation: 13

Lisp recursion confusion

I believe this to be implementation independent, but I use clisp on debian. Below I defined two functions named SUM. They find the sum of two nonnegative integers by adding 1 to N2 and subtracting 1 from N1 until N1 is 0. Approach #1 makes sense to me, but approach #2 is a source of confusion.

;;;Approach #1 (I understand why it works)
> (defun sum (n1 n2) "Return the sum of two nonnegative integers."
      (if (zerop n1) n2 (sum (1- n1) (1+ n2)))) ;1+ adds 1 to it's operator
> (sum 5 10)
1. Trace: (SUM '5 '10)
2. Trace: (SUM '4 '11)
3. Trace: (SUM '3 '12)
4. Trace: (SUM '2 '13)
5. Trace: (SUM '1 '14)
6. Trace: (SUM '0 '15)
6. Trace: SUM ==> 15
5. Trace: SUM ==> 15
4. Trace: SUM ==> 15
3. Trace: SUM ==> 15
2. Trace: SUM ==> 15
1. Trace: SUM ==> 15
15 ;;;The result

This same result can be found using this other approach, which I do not understand but appears to be more common:

> (defun sum (n1 n2) "Return the sum of two nonnegative numbers."
    (if (zerop n1) n2 (1+ (sum2 (1- n1) n2))))
> (sum 5 10)
1. Trace: (SUM '5 '10)
2. Trace: (SUM '4 '10)
3. Trace: (SUM '3 '10)
4. Trace: (SUM '2 '10)
5. Trace: (SUM '1 '10)
6. Trace: (SUM '0 '10)
6. Trace: SUM ==> 10
5. Trace: SUM ==> 11
4. Trace: SUM ==> 12
3. Trace: SUM ==> 13
2. Trace: SUM ==> 14
1. Trace: SUM ==> 15
15

It can be clearly seen that these do something very different and get the same result. How does lisp allow for the behavior in the second approach, and what is the function +1 acting on in the second approach by adding 1 to a function, as a function is not a variable? I got these two functions from chapter 15 of "COMMON LISP: An Interactive Approach"

Upvotes: 1

Views: 109

Answers (1)

Scott Hunter
Scott Hunter

Reputation: 49920

sum2 isn't that different. Both take 1 from n1; the first sum moves it to n2, while the second adds it to the result of the recursive call.

The nice thing about the first sum is that it is tail recursive: it returns just the result of the recursive call, which can be implemented a lot more efficiently (and more closely models a loop).

Upvotes: 1

Related Questions