SoylentNews is people
SoylentNews
Recursion schemes are elegant and useful patterns for expressing general computation. In particular, they allow you to 'factor recursion out' of whatever semantics you may be trying to express when interpreting programs, keeping your interpreters concise, your concerns separated, and your code more maintainable.
...
In this article I want to avoid building up the machinery meticulously and instead concentrate mostly on understanding and using Edward Kmett's recursion-schemes library, which, while lacking in documentation, is very well put together and implements all the background plumbing one needs to get started.In particular, to feel comfortable using recursion-schemes I found that there were a few key patterns worth understanding:
--Factoring recursion out of your data types using pattern functors and a fixed-point wrapper.
--Using the 'Foldable' & 'Unfoldable' classes, plus navigating the 'Base' type family.
--How to use some of the more common recursion schemes out there for everyday tasks.
(Score: 0) by Anonymous Coward on Tuesday December 08 2015, @08:57AM
And has much worse performance, even with tail recursion elimination, because it contains a recursive call that is not tail recursive. The iterative algorithm is O(N), the recursive O(N^2).
Yes, there are ways to resolve this, by adding complexity in the form of memoization, at the cost of O(N) memory where the iterative algorithm has O(1) memory requirement.
But I know, modern programmers don't care about whether their software scales well. Fuck efficiency, fuck memory, elegance is everything! If you run out of memory, just buy more memory. If it is too slow, just buy a faster computer. After all, money is free </sarcasm>
(Score: 0) by Anonymous Coward on Tuesday December 08 2015, @04:38PM
I don't understand the obsession some people have with recursion. As a theoretical concept, it has its uses. As for it being a practical implementation of an algorithm, usually it is lacking (both in space and time measures). Since recursion can always be replaced with iteration, and iteration, even if you need to include a small stack data structure to do the job, is easily understood by even knuckle-dragging programmers, what is the attraction? It seems more like a puzzle to say you did it using recursion and it still performed well.
Maybe it gives academic compiler writers a source of employment (i.e., papers) to continually work on compiler optimizations to undo the programmer's recursion to the iteration that he just could've just used in the first place.
Recursion is OK if used in limited quantities, like salt on food.
(Score: 2) by darkfeline on Thursday December 10 2015, @02:57AM
Actually, if you only memoize the last two calls, the recursive form runs exactly the same as the iterative form (assuming the recursive function calls are optimized).
And obviously, I only used Fibonacci as an example because it's simple and the first thing I thought of, it's practically the worst thing you can do recursively.
"Oh, the worst thing you can do recursively doesn't perform well when done recursively." Yes, thank you very much.
"Oh, why did you choose it if it's not a good example?" Because I wasn't going to spend half an hour trying to think up a good example, and it demonstrates my point that some things are more elegantly EXPRESSED (read: not executed) recursively.
Recursion is a useful programming tool, just like OOP. That doesn't mean you have to force it onto everything you write (but tell that to the OOP folks).
Join the SDF Public Access UNIX System today!