LispForum

hi, trying to write a function that counts odd numbers in a list:
so far
??not sure what to do from this point??
could somebody help?

[ed note: added "

If you're looping over a list, the DOLIST macro is your friend. Also note that (+ 1 sum) calculates a new value but doesn't store it anywhere. Use setf or incf.

ok, so dolist. it doesn't need anything (stop condition, etc) other than the (lst), right? and it will know when the list ends.
where do i initialize the variable sum?right after the dolist?

(dolist (sum (lst)
(sum 0))
(if (t(oddp lst))
(setq sum (+ 1 sum)
(
)

im not sure..

Edit: missed a crucial detail. Tsk.

I'm just a newbie, how is this for a recursive solution:
Is there a simpler way to do this recusively?

hmmmm, recursively....
pretty elegant!

I heard that recursion was a lispy way of doing things, but there could be a better way. I'm not sure if it comes with a performance cost. Perhaps one of the pros can chime in. I'm still trying to get my head around what tail recursion is.

s-imp wrote:I heard that recursion was a lispy way of doing things, but there could be a better way. I'm not sure if it comes with a performance cost. Perhaps one of the pros can chime in. I'm still trying to get my head around what tail recursion is.

Recursion isn't necessarily "more Lispy". Lisp is a multi-paradigm language, so you can do procedural or OOP if you want. IMO, "idiomatic" Lisp has more to do with transforming code, and building the language from bottom-up so that you can express a solution in whatever language is most suitable to the problem.

Recursion, in my limited experience, is always slower than iterating... maybe compiling or using (declare (optimize (speed 1))) would even things up, but I've never tested. Still, if your recursion is the same as the iteration, but with a tail-call and accumulator, I think you can expect a penalty. Again, I could be wrong, and I don't know the whole story.


Tail recursion is when the last call in the function is the function itself. For example, a function that is not tail-recursive might end like this: (cons foo (rec-func (cdr lst)))

In this case, the stack has to unwind before the first iteration can return, which means that for every iteration, the interpreter has to remember all the stack frames that have executed so far.


Here's a more concise (and probably extremely slow) way to do odd counting: (length (remove-if-not #'oddp lst))

Duke wrote: Tail recursion is when the last call in the function is the function itself. For example, a function that is not tail-recursive might end like this: (cons foo (rec-func (cdr lst)))

This is true as stated, but can be generalized. To be a bit more precise, a tail call does not have to be a recursive call to the same function. A tail call is any call where the calling function immediately returns after invoking the callee; the return value of the caller is the return value of the callee. In this case, there is little value in setting up a stack frame when invoking the callee; the caller can jump to the callee and whatever value the callee returns is returned to the code that invoked the caller. The great insight around tail calls was that they allowed compilers to optimize with a simple goto/jmp rather than creating stack frames. This means that a function that calls itself from a tail call (tail recursion) will never run out of stack space. The tail call is effectively a loop written in recursive syntax. But this works when you don't call yourself, too.

If you want to see a great example of this put to use, see Fig. 1 in this paper:
http://www.cs.brown.edu/~sk/Publication ... /paper.pdf

(This is Shriram Krishnamurthi's work on state machines in Scheme that came from his famous Swine Before Perl talk.)

Yeah, I thought about 'length', but I knew to avoid creating cons cells for a new list as you do get a performance penalty for it.

Thank you both for the info on tail-recursion. So my function is not tail recursive (as it calls #'+ last). I traced it and then disassembled it to see what was going on. Very interesting.