Recursion

[David Lees]

Tim,

Real nice explanation.  I was going to post something similar, but yours
is clearer.

Two minor things that come out of playing with recursive and
nonrecursive factorial using PythonWin.  A question and an observation.

1. I notice a pretty low (<999) recursion depth limit for factorial on
Python 2.0.  Can the depth be set easily or does it require recompiling
Python?

2. A simple iterative factorial such as the one one posted by Gerlich
seems to run out of some printing related resource under PythonWin at
values of N around 1400.  Further, the response of PythonWin seems to be
serverly degraded after this.  On the other hand, when I assign the
output of the iterative factorial function to a variable, the result is
computed very rapidly (2 seconds for 10000!).  I can still display the
output by converting it to a string ala:  StringVersion='%s' % x
where x is the 35,660 digit result of 10,000 factorial.

david lees


Tim Peters wrote:
> 
> [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.
> 
<snippity>