Re: recursion performance
- From: Ulrich Hobelmann <u.hobelmann@xxxxxx>
- Date: Tue, 29 Nov 2005 23:53:59 +0100
zion_zii wrote:
Im just starting to program in lisp so please bear with me. As an exercise, I was supposed to write the + function for 2 integers(symbols). This is what I wrote
(defun our+ (n m) (cond ( (zerop m) n) (t (+ (1+ n) (1- m) ) ) ) )
The suggested answer is as follows.
(defun our-add ( n m) (cond ( (zerop m) n) (t (1+ (our-add n (1- m) ) ) ) ) )
My question is this: Is there any difference in performance between the first and the second? Granted, I want to follow what the author has deemed accurate but I dont want to do so blindly. Thanks in advance.
AFAI can see, the suggested version decrements m first (all the way through) and then leaves the recursion, adding the 1 m times.
Your version decrements m and increments n immediately, and then goes on to add them -- wait, your code doesn't recur, i.e. use "our+", but it uses "+". So you're cheating ;)
If you use "our+" instead of "+" the operations are basically the same, but happen in a different order.
Another difference is that the suggested version is recursing, while your version would be tail-recursive, i.e. running in constant space and possibly faster, AFAI can see right now.
Just keep in mind to separate builtin math from the kind of math you're doing here, i.e. don't cheat using builtin "+".
-- The road to hell is paved with good intentions. .
- Follow-Ups:
- Re: recursion performance
- From: Pascal Costanza
- Re: recursion performance
- References:
- recursion performance
- From: zion_zii
- recursion performance
- Prev by Date: Re: OT to the extreme [Was Re: I'm working on yet another license]
- Next by Date: Re: sanity check (coding style)
- Previous by thread: recursion performance
- Next by thread: Re: recursion performance
- Index(es):
Relevant Pages
|
