재귀 함수

재귀 함수란 자기자신을 다시 호출하는 함수를 의미한다.

 

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

 

이 코드를 실행하면 '재귀 함수를 호출합니다' 라는 문자열을 무한히 출력한다. 여기서 정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다. 물론 어느 정도 출력하다가 오류 메시지를 출력하고 멈출 것이다. 

 

 재귀 함수를 쓸 때는 종료 조건이 중요하다. 다음 코드는 i가 100이 될 때 종료한다.

 

def recursive_function(i):
	if i==100:
    return
    print(i)
    recursive_function(i+1)
   
recursive_function(1)

 

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 사용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 

 

따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. DFS가 대표적인 예이다. 

 

재귀 함수에 접근하기 위해서는 2가지 case를 고려해야 한다. 재귀 함수에는 recursive case 와 base case가 있다.

Recursive case : 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우

Base case : 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우

 

예를 들어, some_list라는 배열을 파라미터로 받고, 뒤집힌 리스트를 리턴해 주는 재귀 함수를 만들어보자.

 

먼저 Base case를 생각해보자. Base case는 some_list의 길이가 1이거나 0인 경우이다. Base Case가 종료 조건이라고 생각하면 된다.

 

이때는 아무 조치없이 some_list 자체를 그냥 반환하면 된다. 

 

def flip(some_list):
	#base case
    if len(some_list)==0 or len(some_list)==1:
    	return some_list

 

그리고 현재 문제가 너무 커서 바로 풀지 못하는 경우가 recursive case이다. some_list가 1보다 큰 경우에는 바로 답을 알지 못하기 때문에 부분 문제를 풀어야 된다.

 

def flip(some_list):
    if len(some_list)==0 or len(some_list)==1:
        return some_list
    return some_list[-1:]+flip(some_list[:-1])

 

시간복잡도는 some_list의 길이를 n이라고 하면 some_list[:-1]은 시간 복잡도가 O(n-1)이다.

flip함수는 재귀적으로 n번 실행되고 각 호출은 O(n)이기 때문에 시간 복잡도는 O(n^2)이다.