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'，正确打印返回值，after返回值似乎一直打印无。我错过了什么？

另外，我如何改进程序（继续使用递归）

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

@ Anthony正确回答了您关于 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本身不进行尾递归优化，因此学习手动执行它非常重要。

＆quot;更改[非基本情况]递归步骤'将thisfun（newargs）'返回到 args = newargs;继续并将整个身体放入，而True： loop＆quot;是尾递归优化的基本思想。在这里，我还使li成为非arg（没有理由将其作为arg），在上添加一个条件，并避免 continue ，因为递归无论如何，步骤在身体的尽头。

这个表述将是一个很好的基础，可以进一步优化重构（sqrt避免，memoization，......），以达到更好的性能。

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

没关系。