[Algorithm] 재귀 알고리즘_1

05-1 재귀 알고리즘의 기본

재귀 알아보기

• 재귀(recursion): 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우
• 재귀의 예: 자연수의 정의
  
  • 1은 자연수입니다.
  • 어떤 자연수의 바로 다음 수도 자연수입니다.

---

팩토리얼 알아보기

• 팩토리얼(factorial): 양의 정수를 순서대로 곱한다는 의미로 순차 곱셈이라고도 합니다.
• 재귀를 사용하는 대표적인 예입니다.
• 양의 정수 n의 패토리얼(n!)은 다음과 같이 정의를 할 수 있습니다.
  • 팩토리얼 n!의 정의(n은 양의 정수)
  • 0! = 1
  • n > 0이면 n! = n x (n - 1)!

실습 5-1 양의 정수 n의 팩토리얼 구하기

# 양의 정수 n의 팩토리얼 구하기

def factorial(n: int) -> int:
  """양의 정수 n의 팩토리얼 값을 재귀적으로 구함"""
  if n > 0:
    return n * factorial(n - 1)
  else:
    return 1

if __name__ == '__main__':
  n = int(input('출력할 팩토리얼 값을 입력하세요.: '))
  print(f'{n}의 팩토리얼은 {factorial(n)}입니다.')

출력할 팩토리얼 값을 입력하세요.: 3
3의 팩토리얼은 6입니다.

재귀 호출

3의 팩토리얼값을 재귀적으로 구하는 과정

• [a] 함수 호출식 factorial(3)을 실행하면 factorial() 함수가 호출됩니다. 이 함수는 매개변수 n에 3을 전달받아 3 * factorial(2)의 값을 반환합니다. 그런데 이 곱셈을 하려면 factorial(2)의 값을 구해야 합니다. 그래서 실제 인수로 2를 전달해서 함수 factorial(2)를 호출합니다.
• [b] 호출된 factorial() 함수는 매개변수 n에 2를 전달받습니다. 다시 2 * factorial(1)을 실행하기 위해 함수 factorial(1)을 호출합니다.
• [c] 호출된 factorial() 함수는 매개변수 n에 1을 전달받습니다. 1 * factorial(0)을 실행하기 위해 함수 factorial(0)을 호출합니다.
• [d] 호출된 factorial() 함수는 매개변수 n에 전달받은 값이 0이므로 1을 반환합니다. 이때 처음으로 return 문이 실행되고 반환값 1을 c로 보냅니다.
• [c] 반환된 값 1을 전달받은 factorial() 함수는 1 * factorial(0), 즉 (1 * 1)을 반환합니다.
• [b] 반환된 값 1을 전달받은 factorial() 함수는 2 * factorial(1), 즉 (2 * 1)을 반환합니다.
• [d] 반환된 값 2를 전달받은 factorial() 함수는 3 * factorial(0), 즉 (3 * 2)을 반환합니다.
• 이렇게하면 최종 3의 팩토리얼값인 6을 얻을 수 있습니다.

factorial() 함수는 n - 1의 팩토리얼값을 구하기 위해 다시 자신과 똑같은 factorial() 함수를 호출합니다. 이런 함수의 호출을 재귀 호출(recursive call)이라고 합니다.

직접 재귀와 간접 재귀

• factorial() 함수는 내부에서 자신과 똑같은 factorial() 함수를 호출합니다.
• 자신과 똑같은 함수를 호출하는 방식을 직접 재귀(direct recursion)라고 합니다.
• 간접 재귀(indirect recursion)는 a() 함수가 b() 함수를 호출하고 다시 b() 함수가 a() 함수를 호출하는 구조입니다.

직접 재귀와 간접 재귀

재귀 알고리즘은 풀어야 할 문제나 계산할 함수 또는 처리할 자료구조가 재귀적으로 정의되는 경우에 적용됩니다. 이러한 점에서 재귀 과정으로 팩토 값을 구하는 문제는 재귀의 원리를 이해하기 위한 문제일 뿐 현실적으로는 적절하지 않습니다.

---

유클리드 호제법 알아보기
두 정숫값의 최대 공약수(GCD)를 재귀적으로 구하는 방법을 생각해 봅시다. 2개의 정숫값을 직사각형 두 변의 길이라고 생각하면 두 정숫값의 최대 공약수를 구하는 문제는 다음과 같이 바꿀 수 있습니다.

Q. 직사각형 안을 정사각형 여러 개로 가득 채워 나갑니다. 이렇게 만들 수 있는 정사각형 가운데 가장 작은 정사각형 변의 길이를 구하세요.

22와 8의 최대 공약수를 구하는 과정

1. 위 그림의 a처럼 22 x 8 크기의 직사각형에서 짧은 변의 길이인 8을 한 변으로 하는 정사각형으로 나눕니다. 그러면 b처럼 8 x 8 크기의 정사각형 2개가 만들어지고 8 x 6 크기의 직사각형이 남습니다.
2. 남은 8 x 6 크기의 직사각형에서도 다시 같은 과정을 수행한 결과가 c입니다. 6 x 6 크기의 정사각형 1개가 만들어지고 6 x 2 크기의 직사각형이 남습니다.
3. 남은 6 x 2 크기의 직사각형에서도 다시 같은 과정을 수행한 결과가 d입니다. 이번에는 2 x 2 크기의 정사각형 3개가 만들어집니다. 이렇게 얻은 정사각형의 변의 길이인 2가 8과 22의 최대 공약수입니다.

정리하면 3 과정처럼 두 정숫값이 주어질 때 큰 값을 작은 값으로 나누어 떨어지면 작은 값이 최대 공약수가 됩니다. 나누어 떨어지지 않으면 작은 값과 나머지에 대해 같은 과정을 나누어 떨어질 때까지 재귀적으로 반복합니다.
최대 공약수는 다음과 같이 구할 수 있습니다.

• y가 0이면 ··· x
• y가 0이 아니면 ··· gcd(y, x % y)

이 알고리즘을 유클리드 호제법(Euclidean algorithm)이라고 합니다.
실습 5-2 유클리드 호제법으로 최대 공약수 구하기

# 유클리드 호제법으로 최대 공약수 구하기

def gcd(x: int, y: int) -> int:
  """정숫값 x와 y의 최대 공약수를 반환"""
  if y == 0:
    return x
  else:
    return gcd(y, x % y)

if __name__ == '__main__':
  print('두 정숫값의 최대 공약수를 구합니다.')

  x = int(input('첫 번째 정숫값을 입력하세요.: '))
  y = int(input('두 번째 정숫값을 입력하세요.: '))

  print(f'두 정숫값의 최대 공약수는 {gcd(x,y)}입니다.')

두 정숫값의 최대 공약수를 구합니다.
첫 번째 정숫값을 입력하세요.: 8
두 번째 정숫값을 입력하세요.: 22
두 정숫값의 최대 공약수는 2입니다.

math.gcd() 함수
: 파이썬에서는 최대 공약수를 구하는 표준 라이브러리로 math 모듈에서 gcd() 함수를 제공합니다.

- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file: https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%9E%AC%EA%B7%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb

GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습