Introduction

본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다.

재귀함수

개요

  • 재귀함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미합니다. DFS 구현 시 일반적으로 자주 사용하는 방법 중 하나이므로 이렇게 소개를 하고자 합니다.
def recursive_funct_example():
	print('재귀 함수를 호출합니다.')
	recursive_funct_example()

recursive_funct_example()
# 실행 결과
# 재귀 함수를 호출합니다.
# 재귀 함수를 호출합니다.
# ...
# error 발생합니다.
## 참고로 이런 방식으로 재귀를 하게 되면
## 파이썬은 최대 재귀 깊이 제한이 있으므로 멈추고 초과 메시지를 출력합니다.

재귀 함수의 종료 조건

  • 재귀함수를 문젶 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시하도록 합니다.
  • 이는 함수의 무한 호출을 야기하기 때문입니다.
def recursive_function(i):
	# 100번째 호출 시 종료 되도도록 종료 조건 명시
	if i == 100:
		return
	print(i, '번째 재귀함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
	recursive_function(i + 1)
	print(i, '번째 재귀함수를 종료합니다.')

recursive_function(1)

팩토리얼 구현 예제

  • n! = 1 × 2 × 3 × … × (n - 1) × n
  • 수학적으로 0! = 1! = 1 이 성립합니다.
# 반복적으로 구현 예제
def factorial_iterative(n):
	result = 1
	for i in range (1, n + 1):
		result = result * i
	return result

# 재귀로 구현 예제
def factorial_recursive(n):
	if n <= 1
		return 1
	return n * factorial_recursive(n - 1)

print('반복적 구현 : ', factorial_iterative(5))
print('재귀적 구현 : ', factorial_recursive(5))
# 재귀의 특징인 코드의 간결함이 보여집니다.
# 그러나 재귀적 함수의 경우 성능적인 손해를 본다는 점은 염두해두셔야 할 것입니다.

최대 공약수 계산(유클리드 호제법)예제

  • 유클리드 호제법 : 두 개의 자연수에 대한 최대 공약수를 구하는 대표적인 알고리즘
    • 두 자연수 A, B 에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 합시다.
    • 이때 A, B의 최대공약수는 B와 R의 최대공약수와 같습니다.
  • 유클리드 호제법의 아이디어를 그대로 재귀함수로 작성할 수 있습니다. - 예시 GCD(192, 162)
    단계 A B
    1 192 162
    2 162 30
    3 30 12
    4 12 6 
def gcd(a, b):
	get = a % b
	if get == 0 :
		return b
	return gcd(b, get)

print(gcd(192, 162))

재귀 함수 사용 시 유의 사항

  • 재귀함수를 활용하면 복잡한 알고리즘을 간결하게 작성할 수 잇습니다. 단, 코드의 가독성은 해칠 수 있으므로 신중히 사용해야 합니다.
  • 재귀 반복함수는 반복문과 동일한 기능을 구현한다고 볼 수 있습니다.
  • 재귀 함수가 반복문보다 성능 적으로 유리하거나 불리한 경우가 있습니다.
  • 컴퓨터가 함수를 연속적으로 호출 시 내부 스택 프레임이 쌓이게 되고, 그러다보니 스택을 사용해야 할 때 구현 상 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많습니다.

🧑🏻‍💻 알고리즘 박살내기 시리즈🧑🏻‍💻