4 ms·
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,
by davidtgoldblatt 14y ago
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.
- aroberge 14y agoWhen 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.)
- alexkus 14y agon(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...)
- daniel-cussen 14y agoAnd n(n+1)/2 was only obvious to Euler!
- sesqu 14y agoHardly. It's a simple equation that has been independently discovered for as long as we've had algebra.
- daniel-cussen 14y agoThat'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.
- sesqu 14y agoIt 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.