programme récursif Python au premier factoriser un nombre

Question

j'ai écrit le programme suivant au premier factoriser un nombre:

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 que je reçois:

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

Altho », la valeur retournée est imprimé correctement, la valeur après retournée semble ne pas l'imprimer, tout le temps. Qu'est-ce que je rate?

De plus, comment puis-je améliorer le programme (en continuant à utiliser la récursion)

Answer 1

Votre fonction prime_factorize n'a pas une déclaration de retour dans le cas récursif - vous voulez appeler « prime_factorize de retour (x/i , li) "sur sa dernière ligne. Essayez-le avec un nombre premier (donc l'appel récursif n'est pas nécessaire) pour voir que cela fonctionne dans ce cas.

Aussi, vous voulez sans doute faire quelque chose comme signature:

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

sinon vous obtiendrez des résultats erronés lors de l'appel deux fois ou plus:

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

Answer 2

Une version plus-fonctionnel.

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 3

@ Anthony a correctement répondu à votre question initiale au sujet de print. Cependant, dans l'esprit des quelques conseils qui ont également été offerts, voici une refactorisation simple en utilisant la suppression de récursion 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 traite pas les problèmes de performance cruciales (comportement grand-O est le même que pour votre solution originale) - mais puisque Python lui-même ne fait pas l'optimisation de la récursion de queue, il est important d'apprendre à le faire manuellement.

« Changer le [non-base de cas] récursive les étapes 'return thisfun(newargs)' dans args=newargs; continue et mettre le corps dans une boucle while True: » est l'idée de base de l'optimisation de la queue-récursion. Ici, j'ai également fait un non-arg (pas de raison pour qu'il soit un arg), mettre une condition sur le while, et évité le continue puisque l'étape récursive était à la fin du corps de toute façon. Cette formulation constituerait une bonne base à partir de laquelle appliquer d'autres refactorisations d'optimisation (évitement de carré, mémorisation, ...) pour atteindre de meilleures performances.

Answer 4

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.

Answer 5

Si vous voulez le faire complètement récursif, je recommande ce code, il renvoie la bonne réponse et la façon dont cela fonctionne est assez claire. 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) 

Ceci 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]