berrascht über gute Rekursionsleistung in Pyth

Ich habe diese ziemlich schlechte Python-Funktion für die Primfaktorisierung geschrieben:

import math

def factor(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if not n % i:
            return [i] + factor(n//i)
    return [n]

und es hat wie erwartet funktioniert, jetzt war ich daran interessiert, ob die Leistung bei Verwendung eines iterativen Ansatzes besser sein könnte:

def factor_it(n):
    r = []
    i = 2
    while i < int(math.sqrt(n)+1):
        while not n % i:
            r.append(i)
            n //= i
        i +=1
    if n > 1:
        r.append(n)
    return r

Aber was ich beobachtete (während die Funktionen die gleichen Ergebnisse lieferten) war, dass die iterative Funktion länger brauchte, um ausgeführt zu werden. Zumindest hatte ich dabei das Gefühl:

number = 31123478114123
print(factor(number))
print(factor_it(number))

so habe ich gemessen:

setup = '''
import math

def factor(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if not n % i:
            return [i] + factor(n//i)
    return [n]

def factor_it(n):
    r = []
    i = 2
    while i < int(math.sqrt(n)+1):
        while not n % i:
            r.append(i)
            n //= i
        i +=1
    if n > 1:
        r.append(n)
    return r
'''

import timeit

exec(setup)

number = 66666667*952381*290201
print(factor(number))
print(factor_it(number))

print(timeit.Timer('factor('+str(number)+')',setup=setup).repeat(1,1))
print(timeit.Timer('factor_it('+str(number)+')',setup=setup).repeat(1,1))

Und das habe ich bekommen:

[290201, 952381, 66666667]
[290201, 952381, 66666667]
[0.19888348945642065]
[0.7451271022307537]

Warum ist der rekursive Ansatz in diesem Fall schneller als der iterative?

Ich verwende WinPython-64bit-3.4.4.2 (Python 3.4.4 64bit).

Antworten auf die Frage(2)

Ihre Antwort auf die Frage