[알고리즘] 재귀함수

Daisy 🌼·2022년 7월 26일
0

알고리즘

목록 보기
2/8
post-thumbnail

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

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. 재귀함수 사용의 유의사항

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

profile
세상을 이롭게하는 AI Engineer

0개의 댓글