소수 재귀 - 어떻게 작동합니까? (Python)

Question

숫자가 소수인지 아닌지이 프로그램이 어떻게 알고 있는지 궁금합니다. 나는 소수로 나누는 짝수를 찾기 위해 나머지가 있는지 확인하지만 숫자에는 단지 2 가지 요소 만 있다는 것을 어떻게 알 수 있습니까? 나는 재귀 개념에 익숙하지 않으므로 단계에 대한 설명이 도움이 될 것입니다.

코드

def RecIsPrime(m): 
    """Uses recursion to check if m is prime.""" 
    def PrimeHelper(m, j): 
     """Helper Function to iterate through all j less than m up to 1 to look for even divisors.""" 
     if j == 1: # Assume 1 is a prime number even though it's debatable. 
      return True 
     else: 
      #do this task if both conditionals are true 
      #else break and return false. 
      return m % j != 0 and PrimeHelper(m, j - 1) 
    return PrimeHelper(m, m -1) 

소스

https://github.com/hydrogeologist/LearningPython/blob/master/_recursion%20example%20in%20Python

라인 : 184 그것은 m에서 어떤 번호가 있는지 여부를 확인

Answer 1

194 - 1 분할에 이르기 m, 그냥 짝수를 검사하지 않습니다.

PrimeHelper(10, 9) = 10 % 9 != 0 and PrimeHelper(10, 8) 
↪ PrimeHelper(10, 8) = 10 % 8 != 0 and PrimeHelper(10, 7) 
    ↪ PrimeHelper(10, 7) = 10 % 7 != 0 and PrimeHelper(10, 6) 
    ↪ PrimeHelper(10, 6) = 10 % 6 != 0 and PrimeHelper(10, 5) 
     ↪ PrimeHelper(10, 5) = 10 % 5 != 0 == false 

10 % 5 != 0이 false, 그래서 and의 오른쪽은 evaulated되지 않습니다 :이 중첩 된 기능을해야합니다 RecIsPrime(10)에 대한

EG는, 호출합니다. PrimeHelper(10, 5)은 false을 반환하며 재귀를 계속 수행하지 않습니다.
PrimeHelper(10, 6)에서 은 true이되지만 PrimeHelper(10, 5)은 false 인 것으로 나타났습니다. 그러면 false도 반환되므로 다른 모든 호출도 마찬가지입니다.

Answer 2

이 코드는 꼬리 재귀의 경우입니다. 즉, 반복을 수행하는 재귀 적 방법으로 볼 수 있습니다. 파이썬은 실제로 그것을 (최적화 될 것이다) 그런 식으로 해석하지 않습니다,하지만 그렇게 그것을보고 여전히 도움이된다 :

이

이 PrimeHelper의 모든 재귀 호출이 m에 대해 동일한 값을 갖는 방법 참조 j에 대한 값은 이전 호출에서 사용한 값과 비교하면 1입니다.

따라서 코드는이 변이체에 필적 : 모든 반복이 원래의 코드의 재귀 호출에 대응이 변형에서

def RecIsPrime(m): 
    for j in range(m-1, 1, -1): 
     if m % j == 0: 
      return False 
    return m > 1 

.

PrimeHelper 더 이상

것이 중요하다 호출하지 마십시오 돌아 False

1. : 즉, 거기는 두 가지 목적, 즉 return False 휴식을 원래의 코드에 m % j != 0에 의해 이루어집니다 체인을 참고 인수가 1 이하인 RecIsPrime을 호출 할 때 두 변형이 같은 방식으로 작동하지 않는다는 점에 유의하십시오. 이러한 경우 재귀 코드는 "0으로 나누기" 오류 (RecIsPrime(1) 일 때) 오류 또는 영원히 반복합니다 (예 : RecIsPrime(-1) 또는 그보다 작은 값). 이것은 버그입니다.이 변경 해결하려면 :

   return PrimeHelper(m, m -1) 
   

   도 1의 경우를 해결

   return m > 1 and PrimeHelper(m, m -1) 
   

   에 의해 : 그것은 여부 1 단지 "논쟁의 여지가"보다 많은 것은 소수인지 아닌지 : 그것은 확실히 아니다.