Recursion

[Tim Peters]

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

I'll do what I can, but questions about PythonWin oddities are best directed
at Mark Hammond.

> 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?

import sys
sys.getrecursionlimit()  # returns 1000 by default
sys.setrecursionlimit(n) # to set it

> 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.

See first comment -- I use IDLE out of loyalty to my boss <wink>.

> 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.

A few things to note:

+ Converting a long x to a decimal string (via str(), %s, repr(), whatever)
takes time quadratic in the number of digits in x.  So, e.g., on my box, it
takes about 16 times longer to convert fac(10000) to a decimal string than
to compute it.

+ Converting a long x to a hex or octal string (via hex() or oct() or %x)
takes time linear in the number of digits in x; that's essentially because
longs are stored in base 2**15 internally, and converting that to hex or
octal is trivial.  Continuing the example, converting fac(1000) to a hex
string goes about 1000x *faster* than computing it on my box.  Or, IOW,
converting to hex goes about 10,000 times faster than converting to decimal.
Since N**2/N == 10,000 when N=10,000, this isn't entirely coincidence
<wink>.  So if you're just futzing around, stick to hex.

+ IDLE has no problem displaying fac(10000), so if there is a problem in
PythonWin it's likely to be with the underlying text widget.

+ But IDLE does "bog down" after displaying it, up until the time the last
digit of the display scrolls off the top of the window.  That's true of any
output containing an extremely long single line in IDLE; the Tk text widget
seems to feel abused in such cases (my guess is that the widget's
line-wrapping algorithm is overburdened).

another-millennium-of-widget-excuses-ly y'rs  - tim