[알고리즘/Python] 재귀함수와 팩토리얼

 

재귀적으로 문제를 푼다는것 = 같은 형태의 더 작은 문제를 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 것.

재귀함수의 예시로 팩토리얼을 한번 보자.

 

팩토리얼

 n의 팩토리얼은 n!이라고 표시한다. 이는 1부터 n까지의 정수를 곱하는 단순한 연산을 말한다.

재귀로 풀땐 항상 경우를 나눠줘야하는데 기본적인 base case와 조건이 다른 recursive case가 있다.

0!=1이라고했으니 n =0인 경우는 무조건 n!=1이 된다. 이렇게 바로 답이 나오는 경우를 base case라고 한다.

 

하지만 n != 0 인경우, n >0인 경우엔 재귀적으로 문제를 풀어야한다.

즉,

같은 형태의 더 작은 문제를 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 것이다.

위에 그림처럼  5!은 1x2x3x4x5 =120 이다. 그 안에 1x2x3x4 = 4!이 있다는 것을 알 수 있다.

같은 형태의 더 작은 문제들이 반복되는 경우를 recursive case라고 한다.

 

이를 코드로 바꾸면 이렇게 된다.

# 팩토리얼 재귀함수
def factorial(n):
    if n == 0:
        return 1
    #n이 0이 아닐 경우
    return factorial(n - 1) * n 

print(factorial(5)) # 120




# 팩토리얼 반복문
def factorial(n):
	result = 1
    for i in range(1, n+1):
    	result = result * 1
    return result

print(factorial(5)) # 120

 

여기서 주의!

재귀 함수 호출이 너무 많으면 call stack이 계속 쌓여서 더이상 기록할 공간이 없어지게 된다. 그러면 StackOverflowError가 발생하게 된다. 그 스택오버플로우 맞다.

파이썬은 이를 방지하기 위해서 콜스택을 1000개만 허용하고 있어 이를 넘으면 RecursionError가 뜨면서 프로그램이 중단된다.

 함수호출이 너무 많을것 같다 싶을때는 반복문을 사용하는 것이 더 효율적이다.