재귀 함수를 활용해 숫자가 소수인지 확인하는 파이썬 프로그램

프로그래밍을 배우다 보면 어떤 숫자가 소수(prime number)인지 아닌지 판별해야 하는 경우가 자주 생깁니다. 이 글에서는 재귀(recursion) 기법을 활용해 숫자의 소수 여부를 확인하는 파이썬 프로그램을 예제와 함께 자세히 살펴봅니다.

재귀란 무엇일까요?

재귀는 하나의 함수가 자기 자신을 다시 호출하는 방식으로 동작하는 프로그래밍 기법입니다. 큰 문제를 잘게 나누어 각 부분의 결과를 계산한 뒤, 이 결과들을 결합해 최종 답을 도출합니다. 소수 판별처럼 동일한 연산을 반복 수행해야 하는 문제에 특히 적합한 접근 방식입니다.

예제 코드

아래는 재귀를 사용해 소수 여부를 확인하는 파이썬 코드입니다.

def check_prime(my_num, my_val=None):
    if my_val is None:
        my_val = my_num - 1
    while my_val >= 2:
        if my_num % my_val == 0:
            print("이 숫자는 소수가 아닙니다.")
            return False
        else:
            return check_prime(my_num, my_val - 1)
    else:
        print("이 숫자는 소수입니다.")
        return True

my_num = int(input("확인하고 싶은 숫자를 입력하세요 : "))
print("숫자를 확인하는 중...")
check_prime(my_num)

실행 결과

확인하고 싶은 숫자를 입력하세요 : 46
숫자를 확인하는 중...
이 숫자는 소수가 아닙니다.

코드 상세 설명

• check_prime이라는 이름의 메서드를 정의합니다. 이 메서드는 검사할 숫자(my_num)와 None으로 초기화된 값(my_val)을 매개변수로 받습니다.
• my_val이 None이면, 숫자에서 1을 뺀 값이 할당됩니다. 즉, 처음 호출 시에는 입력값 바로 아래 수부터 검사를 시작합니다.
• my_val이 2보다 크거나 같은 동안, 숫자를 my_val로 나눈 나머지가 0인지 확인합니다.
• 나머지가 0이라면 1과 자기 자신 외의 약수가 존재한다는 뜻이므로, 해당 숫자는 소수가 아니라고 판단하고 False를 반환합니다.
• 나머지가 0이 아니라면, 숫자와 1만큼 감소시킨 값을 인자로 전달하며 메서드를 다시 호출합니다. 이것이 바로 재귀 호출입니다.
• my_val이 2 미만이 되면 더 이상 나눌 수가 없으므로, 해당 숫자는 소수라고 출력하고 True를 반환합니다.
• 함수 외부에서는 사용자에게 검사할 숫자를 입력받습니다.
• 입력받은 값을 인자로 넘겨 함수를 호출하면, 재귀 과정을 거쳐 최종 결과가 콘솔에 출력됩니다.

참고: 성능 개선 팁

위 코드는 n-1부터 2까지 모든 수를 차례대로 검사하므로, 숫자가 커질수록 재귀 호출 횟수가 그만큼 늘어납니다. 실제로는 √n까지만 검사해도 소수 여부를 판별할 수 있으며, 파이썬의 기본 재귀 깊이 제한(약 1000)에 걸리지 않도록 주의해야 합니다. 따라서 큰 수를 다룰 때는 반복문을 사용하거나 √n까지만 검사하도록 최적화하는 것이 더 효율적입니다.