[Python] 재귀 함수(Recursive Function)와 예제(팩토리얼, 이항계수 계산)

재귀 함수

재귀 함수는 함수가 자기 자신을 호출하는 프로그래밍 기법이다.

이는 어떤 문제를 해결할 때 그 문제를 더 작은 부분 문제로 나누고, 각 부분 문제를 해결함으로써 전체 문제를 해결하는 방법이다.

재귀 함수는 일반적인 반복문 대신에 사용되며, 특정 문제를 더 간단하게 해결하기 위해 적합한 경우가 많다.

 

재귀 함수를 사용할 때 주의해야 할 몇 가지 중요한 점이 있다.

 

1. 기저 조건(또는 종료 조건)
   재귀 함수는 무한히 호출되는 것을 방지하기 위해 함수가 종료되는 조건을 가져야 한다.
   기저 조건은 함수가 더 이상 자기 자신을 호출하지 않고 종료되는 지점을 말한다.
2. 스택 사용
   재귀 함수는 호출 스택을 사용한다.
   각 재귀 호출은 스택에 쌓이고 종료 조건에 도달하면 스택에서 제거된다.
   하지만 이러한 스택 사용은 메모리 소비에 영향을 미칠 수 있으므로 재귀 깊이에 주의해야한다.

간단한 예제로 재귀 함수를 알아보자.
팩토리얼을 계산하는 함수를 재귀 함수로 만들어보자.

def factorial(n):
    # 기저 조건
    if n == 0 or n == 1:
        return 1
    # 재귀 호출
    else:
        return n * factorial(n-1)

# 테스트
result = factorial(5)
print(result)

이 함수에서 factorial(n)은 n!을 계산하며, 재귀 호출을 통해 작은 값으로 입력을 바꿔가며 계속 호출한다.

기저 조건은 n이 0 또는 1일 때로 설정하여 더 이상 재귀 호출을 일어나지 않게 하고 1을 리턴한다.

---

재귀 함수를 사용하여 이항 계수 계산해보기

이항계수를 먼저 간단히 알아보자.

이항계수(binomial coefficient)는 조합론에서 사용되는 수학적인 개념으로, 주어진 크기의 집합에서 원하는 개수의 원소를 선택하는 방법의 수를 말한다.

이항계수는 \( \binom{n}{k} \) 또는 \( nCr \)로 쓰며, \( n \)개의 원소를 가진 집합에서 \( k \)개의 원소를 선택하는 경우의 수를 나타낸다.

 

이항계수는 다음의 공식으로 계산된다.

$$nCk = \frac{n!}{k!(n-k)!}$$

그리고 이런 공식도 성립한다.(사실 이 글을 보는 사람은 잘 아는 사실이라고 생각한다.)

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

이제 바로 이 공식으로 이항계수를 재귀함수를 사용하여 구현해보자.

class BinomialCoefficientCalculator:
    def calculate(self, n, k):
        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1
        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        return self.calculate(n - 1, k - 1) + self.calculate(n - 1, k)

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # 이항 계수 계산 및 결과 출력
    calculator = BinomialCoefficientCalculator()
    result = calculator.calculate(n, k)
    print(f"{n}C{k} = {result}")

간단히 설명하자면 \(k\)가 \(0\)이거나 \(n\)일 때 \(1\)을 출력하도록 기저 조건을 설정한다.

 

그리고 이항계수의 성질 \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\)을 사용해서 작아진 입력값을 다시 calculate 함수에 집어넣어 재귀적으로 계산하는 방식이다.

 

코드를 실행하여 적당한 입력을 넣어보자.

실행 결과

---

해결할 문제

\(n\)에 \(30\), \(k\)에 \(15\)을 넣고 돌려보자.

별거 아닐 거 같은 계산인데 꽤 오래 걸리는 것을 확인할 수 있다.

 

시간을 측정하는 코드를 넣고 돌려보자.

import time

class BinomialCoefficientCalculator:
    def calculate(self, n, k):
        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1
        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        return self.calculate(n - 1, k - 1) + self.calculate(n - 1, k)

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # 이항 계수 계산 및 시간 측정
    start_time = time.time()
    calculator = BinomialCoefficientCalculator()
    result = calculator.calculate(n, k)
    end_time = time.time()
    elapsed_time = end_time - start_time

    # 결과 및 시간 출력
    print(f"{n}C{k} = {result}")
    print(f"Time taken to calculate: {elapsed_time} seconds")

입력 값은 \(n=30\), \(k=15\)이다.

코드 실행 시간 측정

내 컴퓨터 기준 (m1 맥북프로 기본형) 약 14초가 걸린다.

 

이 문제는 재귀적으로 계산하면서 작아진 입력에 대한 값을 계산할 때 같은 입력의 값을 여러 번 계산하는 데 있다.

다음 포스팅에서는 이러한 문제를 해결하는 방법에 대해 알아보자.