Re^5: How am i doing?

[hippo]

Yes, you do recall correctly. From section 1.8 of HOP (page 33 in my version):

Sometimes a problem appears to be naturally recursive, and then the recursive solution is grossly inefficient. A very simple example arises when you want to compute Fibonacci numbers. This is a rather unrealistic example, but it has the benefit of being very simple.

[choroba]

> Keep in mind that the classic MIT lectures on programming used to be in Lisp and original Lisp didn't have loops, only those "tail recursions".

I know pretty well, and that's not just Lisp. At $job-2, we had a significant codebase in Erlang, which doesn't have loops, either.

[LanX]

IIRC Fibonacci was also heavily used to show the advantages of Haskell in one of the canonical books.

But unfortunately I never went thru learning Haskell.

[Fletch]

You can define an (infinite, FSVO infinite limited by your patience and available RAM) list without defining a new function, just summing itself with the rest of itself: fibs = 0 : 1 : zipWith (+) fibs (tail fibs), and then you can get the first however many you need with take. Once realized it won't have to recompute anything again.

(I did have to crib from a wiki because I couldn't remember if it was just zip or not.)

[jaredor]

The nerf ball skirmish rages, "What is an apposite non-pedagogical example of recursion?" the casus belli; then, a pause: From a foxhole betwixt comes a plaintive query, "How about Quicksort?"