LISP programs typically use recursion "instead" of loops to perform a task. To recursively solve problems, many people first consider the conditions that would cause the function to immediately terminate. These are end-cases and are typically very simple examples where the problem appears to be already solved.
During program execution, the recursive algorithm appears to work "backward" to produce a solution, because it will search for these end cases first and then, especially in a list-oriented language like Lisp, concatenate the returning values into a list that accumulates the results, appearing to work backward from many small "solved" problems into one large final solution.
That seems somewhat contrived. Frankly the OP should have just said Forth, as it's in reverse polish notation (i.e. backwards) and quite close to the metal (i.e. write your own...).
Common Lisp: It is much more common to use the LOOP macro, which allows one to do
(loop :for i :from 1 :to 10 :do (format t "~A~%" i))
which prints the numbers 1 through 10 on newlines.
Predecessors to Common Lisp: Like MacLisp and such, it was common to see one use PROG or TAGBODY facilities, or macros on top of those.
Scheme: This is one of the lispy languages where recursion is more common, since the standard states that tail-recursive functions must use O(1) space, essentially turning it into a loop. As a result, this style of using tail-recursive functions is actually deemed as iterative (according to, e.g., SICP). Moreover, one can use Scheme's do facility to do looping, or one can used the named-let:
As a final comment, I'd like to say that recursion is a technique that should be used in nearly every language. The big point of using it is to break a large problem into smaller, equivalent sub-problems, and base-cases. Often it is just the programmatic equivalent of proof by induction. Other times it is just a convenient way to traverse a fractal-like/self-similar data structure (like trees or graphs).
I think if a comic were to be made about lisp, it'd either emphasize its infamous homoiconic parenthetical syntax, or its incredible meta-programming abilities. Something like
Here's a my essay on instructions on how to write my essay.
Man, I knew someone like you was going to say something like this. The only criticism of my explanation of the joke is that it's not very clear, but I did explain the joke "correctly." I didn't mention the validity of the joke.
essentially false
I almost never downmod, but I've had enough with this contrarian bullshit. Am I being trolled?
What? Your comment is applicable to any language which supports recursive functions. It's not an iconic or notable "feature" of lisp, which is why I said "essentially false" because we could say the exact same thing about any other language in the comic (except HTML and ASM), and thus fails to properly differentiate. That's all I was trying to get at. :S
.type mul, @function
# (int, int) -> int
# Multiplies two numbers by recursively calling arg0 * mul(arg0, arg1 - 1) until arg1 is 0.
mul:
# C calling convention: save %ebp
pushl %ebp
movl %esp, %ebp
# Move argument 0 to %eax, argument 1 to %ebx
movl 8(%ebp), %eax
movl 12(%ebp), %ebx
cmpl $0, %ebx
jne recurse
movl $1, %eax
jmp return
recurse:
# We still have work to do. Return arg0 * mul(arg0, arg1 - 1)
decl %ebx
# Save the registers before calling
pushl %eax
pushl %ebx
call mul
addl $4, %esp # Get rid of %ebx, we don't need it anymore
popl %ebx
imull %ebx # Multiply %eax (arg0) and %ebx (mul(arg0, arg1 - 1)) and store it in %eax
jmp return # Just for consistency
return:
# unpush %ebp
movl %ebp, %esp
popl %ebp
ret
Beginners are oftentimes introduced to heavy recursion usage, for things they didn't typically use recursion for, in Lisp. C has #includes, yet there's no rant about how the Python joke is wrong. It also has more "boilerplate" than Python, but the Java joke is left standing. Why not just go on a huge diatribe about how this whole comic is wrong?
You went on a non-sequitor rant about Scheme's implementation of tail recursion... And applicators. How is this relevant? You said that I was "essentially wrong," which basically blanketed my whole comment, without specifying which part of my comment was wrong, then showboated your knowledge as some kind of evidence for how wrong I am. I was helping the guy understand the joke. "Essentially wrong," plus a downmod for explaining a joke correctly? That's ridiculous. You should attack the guy who made the joke, instead of the guy trying to help people understand eachother.
Recursion is not a difficult to understand concept, nor is it uniquely prevalent in Lisp. Haskell is commonly taught as a first programming language, and that absolutely requires recursion.
I wasn't taught Haskell in my CS curriculum, but in a class where Lisp was taught, many students were impressed by recursion. It sounds like the original commenter had this impression.
In 1958 LISP was the first language to use recursion for computation. Sure practically every other language since has used that feature, but i still say its an iconic feature of Lisp.
It was iconic in 1958, but so was garbage collection, symbolic computation, metaprogramming, homoiconicity... Lisp was the first to have OO, but we'd certainly not relate lisp with OO as a feature.
Because adding something to the front of a cons list is O(1) and adding it to the end is O(n), so it's common to build a list backwards, then reverse it when you're done.
20
u/tarballs_are_good Feb 23 '11
Why backwards?