[알고리즘] 재귀함수

강의 출처 : 나동빈님 유튜브 강의

1. 재귀함수

• 재귀함수(Recursive Function) : 자기 자신을 다시 호출하는 함수 (DFS 구현 시 자주 사용)
• 단순한 형태의 재귀 예제
  • 재귀 함수를 호출합니다 라는 문자열을 무한히 출력
  • 어느정도 출력하다가 최대 재귀 깊이 초과메시지가 출력됨

def recursive_function():
	print('재귀함수를 호출합니다.')
	recursive_function()

recursive_function()

1-1. 재귀함수의 종료 조건

• 재귀함수를 문제풀이에서 사용할 때는 재귀함수의 종료 조건을 반드시 명시
• 종료조건을 제대로 명시하지 않으면, 함수가 무한히 호출됨

# 종료조건을 포함한 재귀함수 예제
def recursive_function(i):
	if i == 100: # 100번째 호출했을 때 종료되는 조건
		return
	print(i, '번째 재귀함수에서', i+1'번째 재귀함수를 호출합니다.')
	recursive_function(i+1)
	print(i, '번째 재귀함수를 종료합니다.')

recursive_function(i)

1-2. 팩토리얼 구현 예제

# for문으로 반복적으로 구현
def factorial_iterative(n):
	result = 1
	for i in range(1, n+1):
		result *= i
		# 1*1*2*3*4*5 = 120
	return result

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

• 유클리드 호제법 : 두 개의 자연수에 대한 최대공약수를 구하는 대표적 알고리즘
• 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 함
• 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같음
• 유클리드 호제법의 아이디어를 그대로 재귀함수로 작성 가능
  

• 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같음
• 유클리드 호제법의 아이디어를 그대로 재귀함수로 작성 가능

def gcb(a, b):
	if a % b == 0
		return b
	else:
		return gcb(b, a%b) # 이 값이 다시 들어감 (반복)
print(gcb(192, 162))
# 192, 162 -> 192%162 = 30
# 162, 30 -> 162%30 = 12
# 30, 12 -> 30%12 = 6
# 30, 6 -> 30%6 = 0
>>> 6

1-4. 재귀함수 사용의 유의사항

• 재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성가능
• 단 오히려, 다른사람이 이해하기 어려울 수 있으므로 신중히 사용
• 모든 재귀함수는 반복문을 이용해 동일한 기능을 구현가능
• 재귀함수가 반복문보다 유리한 경우도 있고, 불리한 경우도 있음
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임
• 그래서 스택을 사용해야할 때 구현 상 스택 라이브러리 대신 재귀함수를 이용하기도 함