Programme récursif en python pour factoriser un nombre

Question

J'ai écrit le programme suivant pour transformer un nombre en facteurs premiers:

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

Voici le résultat obtenu:

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

Bien, la valeur renvoyée est imprimée correctement, la valeur renvoyée après semble ne rien imprimer, tout le temps. Qu'est-ce qui me manque?

Aussi, comment puis-je améliorer le programme (continuer à utiliser la récursivité)

Answer 1

Votre fonction prime_factorize n'a pas d'instruction return dans le cas récursif - vous souhaitez invoquer & return; prime_factorize (x / i, li) " sur sa dernière ligne. Essayez-le avec un nombre premier (l'appel récursif n'est donc pas nécessaire) pour vérifier qu'il fonctionne dans ce cas.

De plus, vous voudrez probablement que la signature ressemble à:

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

sinon, vous obtenez des résultats erronés lorsque vous l'appelez plusieurs fois:

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

Answer 2

Si vous voulez le faire complètement récursif, je vous recommande ce code, il renvoie la réponse correcte et son fonctionnement est assez clair. Si vous voulez rendre le programme aussi efficace que possible, je vous recommande de vous en tenir à l'une de vos méthodes précédentes.

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

C’est une façon complètement récursive de résoudre votre problème

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

Answer 3

@ Anthony a répondu correctement à votre question initiale sur print . Cependant, dans l’esprit des nombreux conseils qui ont également été proposés, voici une simple refactorisation à l’aide de la suppression de la récursion de la queue:

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

Cela ne résout pas les problèmes de performances cruciaux (le comportement de big-O est identique à celui de votre solution d'origine) - mais comme Python n'optimise pas l'optimisation de la récursion finale, il est important d'apprendre à le faire manuellement.

" Modifiez les étapes récursives [non-case-case-case] 'renvoyez thisfun (newargs)' en args = newargs; continue et place le corps entier dans une boucle while True: " est l'idée de base de l'optimisation de la récursion de la queue. Ici, j'ai aussi fait un argument non argument (aucune raison de le considérer comme argument), posé une condition sur le tant que et évité le continuer puisque le paramètre récursif la marche était quand même au bout du corps.

Cette formulation constituerait une bonne base pour appliquer de nouvelles restructurations optimales (évitement de mémoire, mémorisation, ...) afin d’atteindre de meilleures performances.

Answer 4

Une version plus fonctionnelle.

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