[Section 4] 재귀 함수 예제 _ 팩토리얼 함수 구현하기

파이썬 목차 보기

[Intro] 파이썬 미리보기

0. INTRO

재귀 함수를 글로만 읽는다면 효과적인 이해를 할 수 없으므로 이번에는 팩토리얼 함수를 재귀 함수로 구현해보도록 하자.

1. 팩토리얼 함수 이해하기

팩토리얼 함수는 변수에 대입된 정수를 기준으로 하나씩 감소시킨 값을 곱하고, 그 마지막 곱이 0!(=1)이 될 때까지 자기 자신을 계속하여 곱하는 함수이다. 예를 들어 4! 은 다음과 같다.

 

" 4! = 4 x 3 x 2 x 1"

 

변수를 n으로 나타내고 함수를 f(x)라 하면 팩토리얼 함수는 다음과 같이 나타낼 수 있다.

 

"f(n) = n!"

2. 재귀 함수로 팩토리얼 함수 코드 짜기

재귀 함수는 종료 조건(base case)을 정의하고, 자기 자신을 참조하는 함수이다. 따라서 파이썬 코드로 팩토리얼 함수를 구현하기 위해서 다음과 같이 코드를 짤 수 있다.

 

예시 코드:

def factorial(n):

    if n == 0:

        return 1

    return n * factorial(n-1)

 

n=4

print(factorial(n))

 

코드 결과:

 

팩토리얼 함수 _ 코드 결과

 

4! = 24 가 맞는가? 마... 맞다!!

 

3. 팩토리얼 함수로 확인하는 스택 오버  플로우

이전에 반복과 재귀 함수의 차이점에서 재귀 함수는 스택 영역으로 메모리를 할당하기 때문에 메모리 부족 문제가 발생할 수 있다는 것을 언급한 바 있다. 팩토리얼 함수를 이용하여 재귀 함수의 재호출이 얼마나 많이 일어날 수 있는지 확인해보자. 

 

먼저 n=500인 경우이다.

 

n=500 _ 팩토리얼 함수

 

n= 1000인 경우는?

 

스택 오버 플로우 _ n= 1000

 

1000번 재귀 함수를 반복 사용한 결과는 스택 오버 플로우로 이어졌다. 이 팩토리얼 함수는 n=998일 때부터 스택 오버 플로우가 발생하는데, 통상적으로 재귀 함수는 약 1000번까지 사용이 가능하다고 하니 참고하도록 하자.