Programa recursivo de Python para factorizar un número

Question

Escribí el siguiente programa para descomponer en factores un número:

import math
def prime_factorize(x,li=[]):
    until = int(math.sqrt(x))+1
    for i in xrange(2,until):
        if not x%i:
            li.append(i)
            break
    else:                      #This else belongs to for
        li.append(x)
        print li               #First print statement; This is what is returned
        return li
    prime_factorize(x/i,li)

if __name__=='__main__':
    print prime_factorize(300)   #Second print statement, WTF. why is this None

A continuación se muestra el resultado que obtengo:

 [2, 2, 3, 5, 5]
 None

Altho ', el valor devuelto se imprime correctamente, el valor devuelto después parece no imprimir ninguno, todo el tiempo. ¿Qué me estoy perdiendo?

Además, ¿cómo puedo mejorar el programa (si sigo usando la recursión)

Answer 1

Su función prime_factorize no tiene una declaración return en el caso recursivo: desea invocar " return prime_factorize (x / i, li) " En su última línea. Pruébelo con un número primo (para que la llamada recursiva no sea necesaria) para ver si funciona en ese caso.

También es probable que desee hacer que la firma sea algo así como:

def prime_factorize(x,li=None):
    if li is None: li = []

de lo contrario, obtendrá resultados incorrectos al llamarlo dos o más veces:

>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]

Answer 2

Si quieres hacerlo completamente recursivo, recomendaría este código, devuelve la respuesta correcta y la forma en que funciona es bastante clara. Si desea que el programa sea lo más eficiente posible, le recomiendo que se adhiera a uno de sus métodos anteriores.

def primeFact (i, f):
    if i < f:
        return []
    if i % f == 0:
        return [f] + primeFact (i / f, 2)
    return primeFact (i, f + 1)

Esta es una forma completamente recursiva de resolver su problema

>>> primeFact (300, 2)
[2, 2, 3, 5, 5]
>>> primeFact (17, 2)
[17]
>>> primeFact (2310, 2)
[2, 3, 5, 7, 11]

Answer 3

@ Anthony respondió correctamente su pregunta original sobre print . Sin embargo, en el espíritu de los diversos consejos que también se ofrecieron, aquí hay una refactorización simple usando la eliminación de recursión de cola:

def prime_factorize(x):
  li = []
  while x >= 2:
    until = int(math.sqrt(x))+1
    for i in xrange(2,until):
      if not x%i:
        li.append(i)
        break
    else:
      li.append(x)
      return li
    x //= i

Esto no soluciona los problemas cruciales de rendimiento (el comportamiento big-O es el mismo que para su solución original), pero dado que Python en sí mismo no optimiza la recursividad de cola, es importante aprender a hacerlo manualmente.

" Cambiar los pasos recursivos [no base-case] 'return thisfun (newargs)' en args = newargs; continuar y poner todo el cuerpo en un mientras True: loop " es la idea básica de la optimización de recursión de cola. Aquí también hice que li no sea arg (no hay razón para que sea arg), puse una condición en el while , y evité el continue desde el recursivo el paso estaba al final del cuerpo de todos modos.

Esta formulación sería una buena base para aplicar nuevas refactorizaciones de optimización (evitación de sqrt, memorización, ...) para alcanzar un mejor rendimiento.

Answer 4

Una versión de estilo más funcional.

def prime_factorize( number ):
    def recurse( factors, x, n ):
        if x<2: return factors # 0,1 dont have prime factors
        if n > 1+x**0.5: # reached the upper limit
            factors.append( x ) # the only prime left is x itself
            return factors
        if x%n==0: # x is a factor
            factors.append( n )
            return recurse( factors, x/n, n )
        else:
            return recurse( factors, x, n+1 )
    return recurse( [], number, 2)

for num, factors in ((n, prime_factorize( n )) for n in range(1,50000)):
    assert (num==reduce(lambda x,y:x*y, factors, 1)), (num, factors)
    #print num, ":", factors

Answer 5

def primeFactorization(n):
    """ Return the prime factors of the given number. """
    factors = []
    lastresult = n
    while 1:
        if lastresult == 1:
            break

        c = 2

        while 1:
            if lastresult % c == 0:
                break

            c += 1

        factors.append(c)
        lastresult /= c

    return factors

está bien.