GCD(최대공약수) 구하는 유클리드 알고리즘과 재귀함수, 단순 반복문 비교

 

#유클리드 알고리즘 

 

:  주어진 두 수 사이에 존재하는 최대공약수(GCD-gratest common divisor)를 구하는 알고리즘이다.

두 자연수 a, b (a>b)에 대해서, 

• a 를 b로 나눈 나머지가 0이라면 a와 b의 최대공약수는 b이다.
• a 를 b로 나눈 나머지가 0이 아닌 자연수 r이라면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
• 다시 b와 r에 대한 최대공약수를 구하는 과정을 반복하기 위해서는 재귀함수를 사용해도 되고, 단순 반복문을 사용해도 된다. 

 

 

 

1. 재귀함수로 유클리드 알고리즘을 구현하기

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)

 

 

 

2. 반복문으로 유클리드 알고리즘을 구현하기

def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

 

 

 

이때, 재귀함수와 반복문의 장단점은 다음과 같이 정리할 수 있다.

 

재귀함수

 

장점:

• 코드가 간결하고 직관적이다.
  • 복잡한 문제를 간결하고 이해하기 쉽게 표현할 수 있다.
  • 특히 트리나 그래프 탐색, 분할 정복 알고리즘 등에 유리하다.
  • 문제 자체가 재귀적인 경우, 재귀함수를 사용하면 문제의 구조를 그대로 코드에 반영할 수 있다.

단점:

• 스택 오버플로우 발생 가능, 메모리를 많이 사용함
  • 재귀 깊이가 너무 깊어지면 스택 오버플로우(호출 스택의 한계를 초과하여 발생하는 오류)가 발생해서 프로그램이 작동하지 않을 수 있다.
  • 함수 호출마다 스택 프레임을 생성해서 반복문에 비해 성능이 떨어질 수 있다.

 

단순 반복문

 

장점:

• 효율적이다.
  •  반복문은 일반적으로 재귀함수보다 메모리와 실행 시간이 효율적이다.
• 안정적이다.
  •  스택 오버플로우의 위험이 없다.

단점:

• 코드가 복잡하고 구현이 어렵다.
  • 재귀적인 문제를 반복문으로 푼다면 코드가 더 복잡해지고 가독성도 떨어질 수 있다.

 

 

따라서 재귀함수를 사용할지, 단순 반복문을 사용할지는 문제의 특성과 요구 사항에 따라 적절하게 선택해야 한다.