Python Recursive Program을위한 숫자를 고려합니다

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 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 자체는 꼬리 수익 최적화를 수행하지 않기 때문에 수동으로 수행하는 법을 배우는 것이 중요합니다.

[비베이스 케이스] 재귀 단계를 변경하십시오 'return thisfun(newargs)' ~ 안으로 args=newargs; continue 그리고 몸 전체를 a에 넣습니다 while True: 루프 "는"테일 리퍼 시션 최적화의 기본 아이디어입니다. 여기서 나는 또한 Li가 아닌 것으로 만들었습니다 (Arg가 될 이유가 없음). while, 그리고 피했습니다 continue 재귀 단계가 어쨌든 몸의 끝에 있었기 때문에.

이 제형은 더 나은 성능을 향해 도달하기 위해 추가 최적화 리팩토링 (SQRT 회피, 메모 화 등)을 적용 할 수있는 좋은 기초가 될 것입니다.

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

괜찮아요.