알고리즘) 재귀호출

재귀호출은 함수 안에서 같은 함수를 또 호출하는 것입니다. 

재귀는 문제가 어떤 일정한 규칙이 있는지 살펴보면 됩니다. 

팩토리얼을 봐볼게요

1! = 1

2! = 2 * 1 = 2 * 1!

3! = 3 * 2 * 1  = 3 * 2!

4! = 4 * 3 * 2 * 1 = 4 * 3!

이렇게 n! = n * (n-1)! 형태 입니다. 

이것을 재귀 함수로 표현해보면 

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

점화식도 마찬가지 입니다

대표적인 피보나치를 살펴볼게요

0 1 1 2 3 5 8 13 ....

1 = 0 +1

2 = 1+1

3 = 3 +2

f(n) = f(n-1) + f(n-2) 임을 알 수 있습니다. 

이를 재귀 함수로 표현해보면

def fibonachi(n):
	if n == 0 
    	return 0
    elif n == 1
    	return 1
    return fibonachi(n-1) + fibonachi(n-2)

보통 재귀함수는 시간복잡도가 O(n)인 경우가 많습니다. 함수를 반복해서 n번이나 호출해야 하는 경우가 많기 때문입니다. 

팩토리얼을 보더라도 n-1번 함수를 호출하니 O(n), 피보나치는 2n번 함수를 호출하니 O(2n)입니다. 

 

재귀함수는 정해진 틀이 있습니다. 

# 패턴 1
def function(n):
	if n > 일정값 : # 보통 큰 경우가 많음
    	return function(n-1)
    else : 
    	입력값, 특정값 #재귀호출을 종료하기 위해

# 패턴 2
def function(n):
	if n <= 일정 값 : # 입력값이 일정값보다 작을 때
    	return n, 일정값 # 재귀호출 종료 - 맨 마지막 데이터를 위해 
    return function(n-1)

재귀호출을 하면 내부적으로는 스택처럼 함수가 쌓이게 됩니다.