[코드테스트]재귀함수(Recursion)

 

 

재귀함수는 자기자신을 호출하는 함수를 의미합니다. 

대표적인 팩토리얼 연산을 예로 재귀함수에 대해 알아 봅시다. 

 

팩토리얼 연산

 

팩토리얼연산은 어떤 수와 그보다 작은 수들의 곱을 나타내는 연산으로 

파이썬으로 팩토리얼 연산하는 방법에는 크게 2가지로 반복문으로 구현하는 법 과 재귀함수로 구현하는 방법이 있다.

 

구현방법: 

• 반복문구현
• 재귀함수구현

# 팩토리얼 연산
# n! = n * (n-1) * (n-2) * ... * 1
# 4! = 4 * 3 * 2 * 1

 

팩토리얼 계산: (반복문구현)

def factorial(n):
    
    # 항등원 output 설정
    output = 1
    for i in range(1, n+1):
        output *= i    
    return f'factorial: {output}'

print(factorial(n=2))
print(factorial(n=3))
print(factorial(n=4))
print(factorial(n=5))

#>> factorial: 2
#>> factorial: 6
#>> factorial: 24
#>> factorial: 120

 

팩토리얼 연산: (재귀함수구현)

재귀함수는 수학의 수열의 점화식을 활용한다. 

수열의 점화식이란 이웃한 항의 관계를 통해 수열을 표현하는 것으로 아래와 같은 알고리즘으로 팩토리얼을 재귀함수로 구현한다. 

# 팩토리얼 연산: 점화식 표현
# (n이 1 일 때) 1! = 1
# (n이 2 이상의 수 일 때) n! = n * (n-1)!

 

def factorial(n):

    # (n이 1 일 때) 1! = 1
    if n == 1:
        return 1
    # (n이 2 이상의 수 일 때) n! = n * (n-1)!
    elif n >= 2:
        return n*factorial(n-1)
    
print(f'factorial: {factorial(n=2)}')
print(f'factorial: {factorial(n=3)}')
print(f'factorial: {factorial(n=4)}')
print(f'factorial: {factorial(n=5)}')

#>> factorial: 2
#>> factorial: 6
#>> factorial: 24
#>> factorial: 120