Python递归程序对numb进行素分解

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

但是，返回值被正确地打印出来了，后面的返回值似乎一直没有打印出来。我错过了什么？

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

Answer 1

@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本身不做尾部递归优化，所以学习手动执行非常重要。

“将[non-base case]递归步骤'return thisfun(newargs)'变为args=newargs; continue，将整个身体放入while True:循环”是尾部递归优化的基本思想。在这里，我还将li设为非arg（没有理由将其设为arg），在while上设置一个条件，并避免了continue，因为递归步骤无论如何都在主体的末尾。

这个公式将是一个很好的基础，从中可以应用进一步的优化重构（sqrt避免，记忆化，…）来达到更好的性能。

Answer 2

在递归情况下，prime_factorize函数没有返回语句——您希望在其最后一行调用“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 3

如果你想完全递归，我推荐这段代码，它确实返回了正确的答案，而且它的工作方式非常清楚。 如果你想使程序尽可能有效，我建议你坚持你以前的方法之一。

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]