Reputation: 13
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
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