[알고리즘]재귀함수란?

재귀함수란 무엇일까?

재귀적으로 문제를 푼다?

→같은 형태의 더 작은 문제를 풀고(부분 문제),

부분 문제의 답을 이용해서 기존 문제를 푸는것.

이 때 가장 작은 문제를 base case, 계속 반복되는 문제를 recursive case 라고 한다.

 

 

예) 팩토리얼(!)

 

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! = 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 factorial(n - 1) * n

 

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

반복문도 재귀함수로 표현이 가능하다.

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

-반복문-

def factorial(n):

	result = 1

	i = 1

	for i in range(n+1):

  	result = result * i

return result

 

재귀함수의 단점

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

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

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

 

콜 스택 : 실행중인 함수에 관한 정보가 저장되어 있는 공간.

스택 : Last In First Out(LIFO) 특성을 갖는 자료구조