的Python遞歸程序素比化了許多

我寫了下面的程序，以質比化一些：的Python遞歸程序素比化了許多

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

本書雖然」，返回的值是正確打印，返回後的值似乎一直都不打印。我錯過了什麼？

而且，我怎麼能改善方案（繼續使用遞歸）

來源

2009-09-12 Lakshman Prasad

你prime_factorize功能沒有遞歸情況下return語句 - 你要調用「返回prime_factorize（X/I ，李）「的最後一行。嘗試使用素數（因此不需要遞歸調用）來查看它在這種情況下的效果。

而且你可能想使簽名是這樣的：

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]

來源

2009-09-12 08:05:27

同樣的完全遞歸的方式，'在函數內部print'聲明，你看到的。'None'是函數的返回值。 – 2009-09-12 11:31:31

@ S.Lott，可以解釋一下。我正在返回正在打印的內容。爲什麼它會不同？ – 2009-09-12 16:04:08

而在外面，我正在印刷，我回來了。 – 2009-09-12 16:04:39

功能更強大的風格的版本。

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

來源

2009-09-12 13:59:57

@ Anthony的正確回答了你的原始問題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爲非arg（沒有理由成爲arg），將條件放在while上，並且避免了continue，因爲遞歸步驟在身體的盡頭。

這個公式將是一個很好的基礎，從中可以進一步優化重構（sqrt迴避，memoization，...）以達到更好的性能。

來源

2009-09-12 15:04:33

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

是否正常。

來源

2011-08-09 06:24:34

如果你想完全遞歸，我會推薦這個代碼，它會返回正確的答案，它的工作方式非常清晰。如果你想讓程序儘可能高效，我建議你堅持以前的一種方法。

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]

來源

2012-10-31 21:46:45

的Python遞歸程序素比化了許多

回答

相關問題