Hacker News Reader

Comment by davidtgoldblatt | Hacker News Reader

This is really neither here nor there, but I never understood why factorial is always used as an example of a naturally recursive function, as opposed to, say, sum. It's not as though "product of the numbers from 1 to n" and "sum of the numbers from 1 to n" are somehow inherently different in how recursive they are.

View on HN

When one first encounters factorials, it often is the case that one uses them to calculate ratios of factorials, the simplest bing n!/(n-1)! = n. This example is a natural one to think about recursively. The comparable examples for sums would be the difference of two sums ... and this is rarely done (except perhaps in the case of proofs of the sum of integers from 1 to n, etc.)

n(n+1)/2 also exists as a simple direct method of summing a series of 1..n. There's no similar (obvious) shortcut for n!

(I don't count lgamma as obvious...)

And n(n+1)/2 was only obvious to Euler!

Hardly. It's a simple equation that has been independently discovered for as long as we've had algebra.

That's not the same as being obvious. Obvious means clear at first sight, or clear to a child. If you have to work for it, it's not obvious.

It was clear to me as a child of maybe 8. Granted, in this day and age it's much easier to come up with elementary math, but I would say that particular equation meets the obviousness criterion of patent law, based on the aforementioned historical evidence.

Reply on news.ycombinator.com