[Tutor] global variables & recursion (& stackless)

[Gregor Lingl]

Karl Pflästerer schrieb:

>ACK.  After having looked at your second solution I tried a solution
>which makes it IMO clearer how s and t are found (in the original code
>it was a bit hidden IMO).
>
>def gcd (a, b):
>    a, b = abs(a), abs(b)
>    rem = []
>    while b > 0:
>            rem.append((a,b))
>            a, b = b, a%b
>    return a, rem
>
>def st (a, b):
>    gc, rem = gcd(a, b)
>    rem.reverse()
>    s = t = 1
>    for a, b in rem:
>       s, t = t, s - (a//b)*t
>    return gc, (a, s), (b, t)
>
>
>  
>
That's a fine solution....
mine was directly derived from alice's,  using her  recursive approach
and (intentionally) making only slight modifications. Certainly  alice 
will be pleased
to see  her  solution  now turned into a iterative one. 

>The gcd function is nearly the standard solution (only the rem[] list is
>additional).
>
>The st() function then uses that function to compute s and t.
>
>
>Recursion is a very useful technique but in Python sadly not very
>performant (what about Stackless in that regard?).  
>
I'v timed the performance of gcd roughly with:

 >>> if 1:
    t1 = clock()
    for a in range(1,1001):
        for b in range(1,a):
            x = gcd(a,b)
    print clock()-t1

This computes approx 500000 gcds

Results:

function           Python2.2      Python2.3.3    Python2.3.3-Stackless3.0
ggt-iterative       2.20 s           2.10 s          1.62 s (!)
ggt-recursive       2.40 s           2.45 s          2.30 s

So in this case the performance issue concerning iterative versus
recursive seems to be of minor importance

Regards, Gregor

P.S. time used by the naked loops + assignment:

if 1:
    t1 = clock()
    for a in range(1,1001):
        for b in range(1,a):
            x = b
    print clock()-t1

needs approx.  0.2s 

>That should be told
>anyone who uses recursive algorithms so they are rewritten iteratively
>(if possible).
>  
>