[알고리즘]재귀함수

재귀적으로 문제를 푼다?

->같은 형태의 더 작은 문제를 풀고(부분 문제), 부분 문제의 답을 이용해서 기존 문제를 푸는것

 

예) 팩토리얼(!)

 

4!을 구하기 위해서는

 

4! = 4 x 3 x 2 x 1 ☞ 3! 값이 필요하다.

           = 3!

 

3! = 3 x 2 x 1 ☞ 2! 값이 필요하다.

           = 2!

 

2! = 2 x 1 ☞ 1! 값이 필요하다

         = 1!

 

1! = 1 x 0

         = 0!

0 ! = 1

 

4!을 구하기 위해 필요한 부분문제들이 모두 풀렸으므로,

각 결과들을 역순으로 이용하여 값을 도출한다.

 

0! = 1 임을 이미 알고 있으므로, 재귀함수에 설정을 해놓고

n = 0 인 경우에는 값이 1이 도출되도록 한다.

 

n =  0 인 경우, n! = 1 -> base case (가장 단순한 계산. 가장 마지막에 남는 기초 계산)

n > 0 인 경우, n! = n x (n - 1)! -> recursive case (반복되는 계산)

 

재귀함수를 이용하기 위해서는 recursive case가 어떻게 되는지 생각하고, base case 까지

모두 설정해야 한다.

파이썬 예시 코드 - 재귀함수(팩토리얼 계산)

def factorial(n):
	if n == 0:
    	return 1
    return n * factorial(n-1)

파이썬 예시 코드 - 반복문(팩토리얼 계산)

def factorial(n):

result = 1
i = 1

for i in range(n+1):

  result = result * i

return result

 

재귀 함수는 반복문으로도 표현이 가능하며, 반복문도 재귀함수로 표현이 가능하다

때에 따라 적당히 선택해서 사용하면 된다.

 

재귀함수의 단점

: 함수의 내부적인 동작 방식을 먼저 알아야 한다.

콜스택이 너무 많이 쌓이면 재귀함수를 실행하는데에 시간이 매우 많이 걸린다.

파이썬에서는 콜스택을 1000개 까지로 제한한다.(n <= 1000)

 

＊콜스택 : 실행중인 함수가 저장되어있는 공간