Рекурсивная программа 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 не имеет оператора return в рекурсивном случае - вы хотите вызвать «return prime_factorize (x / i, 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 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]

Answer 3

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

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

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

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

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

Answer 4

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

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

все нормально.