On Tue, Apr 19, 2011 at 4:42 PM, Jussi Piitulainen <jpiit...@ling.helsinki.fi> wrote: > Factorials become an interesting demonstration of recursion when done > well. There's a paper by Richard J. Fateman, citing Peter Luschny: > > <http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf> > <http://www.luschny.de/math/factorial/FastFactorialFunctions.htm> > > Fateman's "major conclusion is that you should probably not use the > 'naive' factorial programs for much of anything". I take this to > include their use as examples of recursion, unless the purpose is to > make the idea of recursion look bad.
" And here is an algorithm which nobody needs, for the Simple-Minded only: long factorial(long n) { return n <= 1 ? 1 : n * factorial(n-1); } Do not use it if n > 12. " I suppose the n > 12 issue is based on the assumption that sizeof(long)==4. That's not an algorithmic question, that's a return type issue... not to mention a rather naive assumption. 64-bit integers let you go to n == 20 (iirc), and if you go bignum, even that simple algorithm will be fine for up to n == 500 or so without stack issues. But sometimes you need a simple and well-known algorithm to demonstrate a language feature with. Maybe we should switch to Fibonacci instead... Anyone for caramel sauce? http://www.dangermouse.net/esoteric/chef_fib.html (As a side point, I have become somewhat noted around the house for always saying "Fibonacci" whenever caramel sauce is mentioned...) Chris Angelico -- http://mail.python.org/mailman/listinfo/python-list