[알고리즘][파이썬] 재귀함수 / Recursive Function

알고리즘 공부하다가.. 한 번 정리해둬야겠다 싶은 재귀함수

레쮸고

---

재귀함수 (Recursive Function)

• 자기 자신을 호출하는 함수
• 프랙털(Fractal) 구조와 흡사

---

기본 예제

def recursive():
	print("재귀 함수 호출")
    recursive()
    
recursive()

위와 같이 코드 실행 시 "재귀 함수 호출" 문자열이 계속 출력되다가 오류 메세지가 출력된다.

"RecursionError: maximum recursion depth exceeded while pickling an object"

재귀의 최대 깊이를 초과했다는 내용으로 파이썬 인터프리터는 호출 횟수 제한이 있기 때문에 생기는 오류이다.

(프로그래밍 대회에서는 파이썬의 재귀 호출 제한을 처리하기 위해 라이브러리를 사용하기도 한다.)

---

종료 조건

종료 조건 없이 재귀 함수 사용시 함수가 무한 호출되어 위와 같은 오류 메세지가 출력될 수 있다.

가장 간단한 예시는 if문을 이용해 종료 조건을 명시할 수 있다.

def recursive_function(i):
	if i == 100: #종료조건
    	return
    print(i, "번째 재귀 함수에서", i+1, "번째 재귀 함수를 호출")
    recursive_function(i+1)
    print(i, "번째 재귀 함수 종료")

recursive_function(1)

---

재귀함수의 수행

• 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문에
• 재귀 함수는 내부적으로  스택 자료구조와 동일
• 따라서 스택 자료구조를 활용해야 하는 알고리즘이 재귀 함수를 통해 간편하게 구현 가능
• 대표적인 예시 : DFS, 팩토리얼 등

# 반복 구현
def factorial_iterative(n):
	result = 1
    for i in range(1, n+1):
    	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))

(10째줄에..간격이안맞는다..)

• 재귀적으로 구현한 코드가 더 간결함을 확인 가능 => 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문

---