[알고리즘 이론] 재귀 용법 (Recursive Call, 재귀 호출)

재귀 용법(Recursive Call, 재귀 호출)

• 함수 안에서 동일한 함수를 호출하는 형태
  • 파이썬에서는 재귀 함수 깊이가 1000 이하가 되어야 한다,
  • 종료 조건이 항상 있어야 한다,
• ⚠️ 재귀 용법 사용 시 주의할 점!
  • 파이썬에서는 재귀 함수 깊이가 1000 이하가 되어야 한다,
  • 종료 조건이 항상 있어야 한다,
• 재귀 함수는 내부적으로 스택처럼 관리된다.

출처: fastcampus

 

 

재귀 용법의 일반적인 형태

""" 일반적인 형태 1 """

def function_1(입력):
	if 입력 > 일정값: # 입력값이 일정 값 이상이면
		return function(입력 - 1) # 입력값보다 작은 값
	else:
		return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료

""" 일반적인 형태 2 """

def function_2(입력):
	if 입력 <= 일정값: # 입려값이 일정 값보다 작으면
		return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료
	function(입력보다 작은 값)
	return 결과값

 

예시) 팩토리얼(factorial)

""" 규칙 생각하기! """
# n! =  n x (n-1)!

def factorial_1(n):
	if n > 1:
		return n * factorial_1(n-1)
	else:
		return n

def factorial_2(n):
	if n <= 1:
		return n
	else:
		n * factorial_2(n-1)

 

예시) 1부터 num까지의 곱을 출력하는 함수

def multiple_without_recursion(num):
	result = 1
	for i in range(1, num+1):
		result = result * i
	return result

# 재귀 사용
def multiple_with_recursion(num):
	if num <= 1:
		return num
	return num * multiple_with_recursion(num-1)

 

예시) 리스트의 합을 리턴하는 함수

def sum_with_recursion(data):
	if len(data) <= 1: # 리스트의 원소가 1개일 경우
		return data[0]
	else:
		return data[0] + sum_with_recursion(data[1:])