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]