(재귀함수) $n!$ ($n$ 의 계승) 구하기

재귀함수(recursive function) 이란 함수내에서 자기 자신을 호출하는 함수이다. 재귀함수가 어떤 식으로 동작하는지는 재귀함수를 이용하여 $n!$ 을 구해보면 쉽게 알 수 있다.

$n!$ 은 혹은 $n$ 의 계승은 다음과 같이 $1$ 부터 $n$ 까지의 곱으로 정의된다.

$$ n! = \prod \limits_{k=1}^n k= n \times (n-1) \times \cdots \times 2 \times 1$$

물론 루프(loop)를 이용하여 $n!$ 을 구할 수 있지만, 재귀함수를 이용할 수도 있다. 

재귀함수를 이용한 $n!$ 구하기 파이썬 코드는 다음과 같다.

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

num = input("계승을 구하고자 하는 자연수를 입력하세요 : ")
print(factorial(int(num)))

factorial 함수의 return n * factorial(n - 1) 부분에서 자기 자신을 호출하고 있는 것을 볼 수 있다.

$4!$ 을 재귀함수를 이용하여 구하는 과정을 그림으로 나타내면 다음과 같다.

$4!$ 을 구하기 위하여 factorial(4) 를 호출하게 되면 4 * factorial(3) 을 반환하기 때문에 다시 factorial(3) 이 호출된다. 

$3!$ 을 구하기 위하여 factorial(3) 이 호출되면 3 * factorial(2) 을 반환하기 때문에 다시 factorial(2) 가 호출된다.

$vdots$

이런식으로 계속 factorial 함수가 호출되다가 factorial(0) 이 호출되면 $1$이 반환되면서 그림에서와 같이 최종적으로 $1$ 부터 $n$ 까지의 곱이 반환된다.

실행결과는 다음과 같다.

계승을 구하고자 하는 자연수를 입력하세요 : 4
24

이렇듯 재귀함수는 자기 자신을 호출하면서 계층적으로 $n!$ 을 계산해내게 된다. 

이 예제만 보면 재귀함수가 그렇게 이해하기 어려운 함수는 아닌것 같다.

하지만 좀 더 복잡한 문제에서 재귀함수가 쓰일 경우, 재귀함수가 어떻게 작동하는지 이해하는 것 조차도 어려운 경우가 많다.

따라서 재귀함수를 이해하거나 혹은 재귀함수를 사용할 때에는 반드시 위와 같은 그림을 그려가면서 그 작동 원리를 이해하는 것을 추천한다.