"In math and engineering, recursion, especially, is a big win. Inductive proofs are wonderfully short. In software, a problem that can be solved by recursion is nearly always best solved that way."
I don't make use of recursion very often but this statement doesn't sound right to me. Actually the opposite seems right. If you read the chapter on recursion from Concrete Mathematics (I'm thinking about the The Tower of Hanoi, Lines in the Plane and The Josephus Problem here, it seems obvious that a closed form is much faster, simpler and according to the blog post more beautiful. Does anybody with more extensive knowledge on the topic care to comment on this?
I find inductive proofs tend to leave me hanging - I become convinced that the conclusion is true, but I still have no intuition as to why. For example, Wikipedia's proof [0] that sum of 0..n == n(n+1)/2 is convincing, but unenlightening. There are proofs which seem much more "elegant" to me, for example, pairing (1+n) == (2+n-1) == (3+n-2) ... (n/2 + (n/2 + 1)) [1], or constructing triangles [also 1].
The book I mentioned above, Concrete Mathematics, talks about how to develop an intuition when it comes to induction. One of the advice mentioned is to always start with smallest cases possible because that makes the problem easier to understand. I suppose the more you practice the better your intuition becomes.
You say "closed form" which sounds alot like the javascript representation of "clousure". And I also remember the javascript "memoizer" way to solve the Fibonacci sequence. How do you exactly define "closed form" and are there any solutions that cannot be optimized by defining in such a form?????
By closed form I mean basically, "You can write down a formula."
A trivial example of a problem that cannot be solved in closed form is to construct a sequence x(n) with x(0) = 1, x(1) = x(2) = x(3) = x(4) = 0, and x(n+5) = x(n+1) - x(n). There does happen to be a formula, but it is in terms of the roots of a 5th degree polynomial whose roots cannot be written with radicals.
A more interesting class of problems is solving for f(x) = y with complicated functions f. Assuming that f is continuous, we can use binary search recursively until our answer is good enough. But generally there is no analytical answer.
Then there are problems that we can tackle with recursion on top of recursion. For example suppose that we want a numerical solutions to a non-linear first order differential equation with specified values for f(0) and f(1). It is straightforward to recursively calculate the trajectory with specified f(0) and f'(0). (For example http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods work well.) Then we can set up binary search to find the right value of f'(0) to get the desired f(1). This is not even a particularly complicated program to write, especially if you've got closures in your language. But trust me when I say that we have no hope of solving this analytically.
(A more complicated version of this technique is used to calculate what the masses of planets must be based on their gravitational influence on other planets over a very long time.)
I don't make use of recursion very often but this statement doesn't sound right to me. Actually the opposite seems right. If you read the chapter on recursion from Concrete Mathematics (I'm thinking about the The Tower of Hanoi, Lines in the Plane and The Josephus Problem here, it seems obvious that a closed form is much faster, simpler and according to the blog post more beautiful. Does anybody with more extensive knowledge on the topic care to comment on this?