Recursion

[Tim Peters]

[Bob Calco]
> ...
> def factor(N):
>   n = 1L
>   for i in xrange(1,N+1):
>     n *= i
>   return n
>
> I tried it with 5000, and then 10000, and while it isn't super fast
> in either case, and seemed more than twice as slow at 10000 than
> 5000, it sure did work.

Your observations are on target but your intuition is off base:  the time it
takes to multiply two C ints is (on most modern machines) independent of
their values.  But the time to multiply two unbounded ints (the way Python
does it) is proportional to the product of the number of bits in each.
Here, work these two out "by hand", and time yourself:

2 * 3
98 * 57

I'm betting the second one took more than twice as long as the first one
<wink>.  Then try

2309874023984023908293 * 821768768768726487687682364876328

by hand.  So, yes, factor(10000) will be substantially more than twice as
slow as factor(5000) -- the former eventually has to deal with much larger
numbers, and larger numbers cost more to operate on.

> ...
> If I were trying to do this in C or Object Pascal, I don't think
> I'd have made this error even if I were completely smashed drunk.
> For one thing, the compilers wouldn't let me...

Most C compilers would have let you get away with

int factor(int n) {
     if (n == 1) return 1;
     return n * factor(n-1);
}

at both compile- and run- times, since few C runtimes even have options to
let you check for int overflow.  Python differs in that respect.  It was a
natural trap for you to fall into!

> While I like the idea of teaching programming concepts with high
> level languages, there's still no substitute for real C (even
> Assembly) experience,

We still implement Python in C, too <wink>.

> and no reason whatsoever to believe that such experience would
> not be most helpful in really mastering even a simple but subtle
> script language like Python. "Apply what you know" -- if that's
> the sign of intelligence, I just got humbled. :/

Speaking of which (C, not humble pie), another thing for you to consider is
the ease of extending and embedding your language of choice with/in C.
Python has an excellent story there; Perl currently does not; unsure about
Ruby.

python-is-to-bliss-as-alcohol-is-to-hangovers-ly y'rs  - tim