News for hackers. Stuff that matters.
Re:PG on the cover of Forbes by axod on Friday November 19, 2010 @04:46AM (#1920963)
afaik it's pretty academic. The only practical application is to allow recursion in languages that don't do recursion which is pretty much none.

This is a good description if you're into that sort of thing: http://mvanier.livejournal.com/2897.html

The meat of it is that you can 'do' recursion by building up functions that call other functions :/ meh

Re:PG on the cover of Forbes by ericb on Friday November 19, 2010 @07:21AM (#1921201)
Wow, hmm.. I worked a MEDITECH a long time ago, and they actually used a programming language, MAGIC, that you couldn't recurse in. It used macro code expansion to take MAGIC code and output into a lower level language and recursion would make it loop infinitely. Maybe at MEDITECH it wouldn't have been so academic.

Edit: Not sure why this got downvoted, but in their internal programming course they talked about the recursion problem explicitly--I'm not making this up, as crazy as it sounds.

If you don't believe me, here is a link to a blog post with someone else mentioning it in the comments:

http://htmlcoderhelper.com/what-is-the-worst-programming-lan...

Re:PG on the cover of Forbes by axod on Friday November 19, 2010 @10:54AM (#1921704)
Why is it an issue though? Recursion is an optional thing some programmers like using. It's not necessary.

edit: rather than downmod me to -1 for stating a fact, why not reply?

Re:PG on the cover of Forbes by smanek on Friday November 19, 2010 @06:18PM (#1923231)
That's like saying integers are an optional thing, and it's no big deal if your programming language doesn't have them. True, they aren't necessary (look at peano arith or pure lambda calc) - but it sure makes things a lot easier. It's much more concise and intuitive to write some search or divide and conquer algos recursively than imperatively.
Re:PG on the cover of Forbes by axod on Saturday November 20, 2010 @02:59AM (#1924097)
javascript doesn't have an integer type.

Possibly it makes things easier for some algorithms, but as I said, it is optional. It's not rocket science to rewrite any algorithm that relies on recursion to not need it.

Re:PG on the cover of Forbes by spacemanaki on Friday November 19, 2010 @08:30AM (#1921335)
The "meat" of it is really that (Y F) = (F (Y F)). In other words Y applied to a function F expands to F applied the original expression, so it builds up nested calls of F.

I can't do it justice, but it's definitely much more interesting and even beautiful than "meh". I guess there are always "practical" vs "academic" arguments to be made but I find stuff like the lambda calculus, Y, Church numerals, all really cool.

Re:PG on the cover of Forbes by axod on Friday November 19, 2010 @09:56AM (#1921533)
Yeah ok, it's sort of interesting as a curiosity. But it's going to be terribly inefficient if used, and doesn't really have any practical application.

I've always been more of a practical "why not just use a loop" kinda guy, so it's probably wasted on me.

Re:PG on the cover of Forbes by abstractbill on Friday November 19, 2010 @10:57AM (#1921717)
Right, it's not really supposed to be used, but it's impressive and interesting in the same way that e^πi = -1 is.
Re:PG on the cover of Forbes by axod on Friday November 19, 2010 @11:59AM (#1921899)
I didn't really find that. It's just functions calling other functions. How exciting can that get :/
Re:PG on the cover of Forbes by abstractbill on Friday November 19, 2010 @02:13PM (#1922398)
If you told me (before I knew about the Y combinator) that there was a function Y such that Y(F) = F(Y(F)) for every other function F, I doubt I would have believed you.
Re:PG on the cover of Forbes by eru on Friday November 19, 2010 @10:59AM (#1921721)
Loops are just a special case of recursion, and only necessary for languages that don't support recursion very well. As an example, Scheme and Haskell have no use for loops.
Re:PG on the cover of Forbes by axod on Friday November 19, 2010 @11:55AM (#1921877)
Loops are how most people think. They're also how most CPUs think.

It seems to me logical for both parties to express programs mostly using loops.

Re:PG on the cover of Forbes by timtadh on Friday November 19, 2010 @03:44PM (#1922726)
Except there is no difference at the machine instruction level between a recursive and iterative approaches. They are isomorphic to each other. That is why you can implement all recursive algorithms using an explicit stack and a loop and all iterative algorithms as recursive functions.
Re:PG on the cover of Forbes by axod on Friday November 19, 2010 @05:35PM (#1923093)
Huh?

There's a lot of difference in the unoptimized form of recursion - namely stack usage. Yes you can hack together tail call recursion to try and make recursion perform as well as iteration does, but what really is the point?

Re:PG on the cover of Forbes by eru on Monday November 22, 2010 @09:43AM (#1929896)
The concept of recursion in is independent of computers. Recursion is just the mathematicians idea of how to repeat get arbitrarily big objects out of limited definitions.

Loops are a just a special case, and not really closer to the hardware. Branches and jumps are closer to the hardware. "Yes you can hack together [a compiler] to try and make [structured programming] perform as well as [goto] does, but what really is the point?"

Re:PG on the cover of Forbes by simplegeek on Friday November 19, 2010 @05:14AM (#1921000)
>> The only practical application is to allow recursion in languages that don't do recursion which is pretty much none.

Above is a very hard sentence to parse for non-native speakers, just saying ;)

Re:PG on the cover of Forbes by eru on Friday November 19, 2010 @10:57AM (#1921719)
I did not have too hard a time. But the sentence is not a model of clarity.
Re:PG on the cover of Forbes by axod on Friday November 19, 2010 @12:07PM (#1921921)
... such is my brain.