Feature suggestion -- return if true

Chris Angelico rosuav at gmail.com
Tue Apr 19 09:01:59 CEST 2011


On Tue, Apr 19, 2011 at 4:42 PM, Jussi Piitulainen
<jpiitula at 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



More information about the Python-list mailing list