Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #3544

Re: Feature suggestion -- return if true

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Feature suggestion -- return if true Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-04-17 16:21 +1200
  Re: Feature suggestion -- return if true Chris Angelico <rosuav@gmail.com> - 2011-04-17 14:31 +1000
  Re: Feature suggestion -- return if true Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-04-17 08:45 +0000
    Re: Feature suggestion -- return if true Chris Angelico <rosuav@gmail.com> - 2011-04-17 19:07 +1000
      Re: Feature suggestion -- return if true Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-04-17 15:23 +0000
    Re: Feature suggestion -- return if true Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-04-18 12:25 +1200
    Re: Feature suggestion -- return if true Dave Angel <davea@ieee.org> - 2011-04-17 22:04 -0400
    Re: Feature suggestion -- return if true Chris Angelico <rosuav@gmail.com> - 2011-04-18 12:10 +1000
      Re: Feature suggestion -- return if true Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-04-19 12:35 +1200
        Re: Feature suggestion -- return if true Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2011-04-19 09:42 +0300
          Re: Feature suggestion -- return if true Chris Angelico <rosuav@gmail.com> - 2011-04-19 17:01 +1000
  Re: Feature suggestion -- return if true "D'Arcy J.M. Cain" <darcy@druid.net> - 2011-04-17 08:33 -0400
    Re: Feature suggestion -- return if true Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-04-17 15:10 +0000
    Re: Feature suggestion -- return if true aahz@pythoncraft.com (Aahz) - 2011-04-18 09:11 -0700
  Re: Feature suggestion -- return if true Greg Ewing <greg.ewing@canterbury.ac.nz> - 2011-04-18 11:09 +1200

csiph-web