Python рекурсивная программа для простого факторизовать ряд

Question

я написал следующую программу в прайм факторизовать номер:

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 

Ниже приведен результат я получаю:

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

Altho», возвращаемое значение правильно напечатан, после возвращаемого значения все время печатается. Что мне не хватает?

Кроме того, как можно улучшить программу (продолжая использовать рекурсию)

Answer 1

Ваша функция prime_factorize не оператор возврата в рекурсивном случае - вы хотите, чтобы вызвать «обратный prime_factorize (х/я , li) "на последней строке. Попробуйте с простым номером (так что рекурсивный вызов не нужен), чтобы увидеть, что он работает в этом случае.

Кроме того, вы, вероятно, хотите сделать что-то подпись, как:

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

иначе вы получите неправильные результаты при вызове его два или более раз:

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

Answer 2

Более функциональный стиль версия.

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

@ Антони правильно ответил на ваш первоначальный вопрос о print. Однако, в духе несколько советов, которые также были предложены, вот простой refactorization с использованием функции удаления хвоста рекурсии:

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 

Это не решает ключевые проблемы производительности (поведение большой-O такая же, как для вашего оригинальное решение), но поскольку сам Python не выполняет оптимизацию хвостовой рекурсии, важно научиться делать это вручную.

«Изменение [без базового случая] рекурсивные шагов 'return thisfun(newargs)' в args=newargs; continue и поместить все тело в while True: петли» является основной идеей хвостовой рекурсии оптимизации. Здесь я также сделал li non-arg (нет причин для этого быть arg), положил условие на while и избежал continue, так как рекурсивный шаг был в конце тела в любом случае.

Эта формулировка будет хорошей основой для применения дальнейших оптимизационных рефакторингов (избежание sqrt, memoization, ...) для достижения лучшей производительности.

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 

в порядке.

Answer 5

Если вы хотите сделать это полностью рекурсивным, я бы рекомендовал этот код, он вернет правильный ответ и способ его работы довольно ясен. Если вы хотите сделать программу максимально эффективной, я бы рекомендовал вам придерживаться одного из ваших предыдущих методов.

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

Это полностью рекурсивный способ решения вашей проблемы

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