[Python] 재귀함수

---

💡 재귀함수란? 자기 자신을 다시 호출하는 함수

def recursive_function():
    print('재귀 함수를 호출합니다.')
    recursive_function()
recursive_function()

 

'재귀 함수를 호출합니다' 라는 문자열을 무한히 호출한다.

 

✔️ 재귀함수의 종료 조건

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날 지, 종료 조건을 꼭 명시해야 한다.

 

def recursive_function(i):
    if i == 100 : return
    print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
    recursive_function(i + 1)
    print(i, '번째 재귀 함수를 종료합니다.')
    
recursive_function(1)

 

 

컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용한다.

함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

 

재귀 함수를 이용하는 대표적인 예로 팩토리얼 문제가 있다.

 

✔️ 반복적으로 구현

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

factorial_iterative(5)	# 120

 

✔️ 재귀적으로 구현

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n-1)

factorial_recursive(5)	# 120

재귀 함수는 수학의 점화식을 그대로 소스코드로 옮겨 더 간결하다.

점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것이다.

 

수학의 점화식

1) n이 0 혹은 1 일 때 : factorial(n) = 1
2) n이 1보다 클 때 : factorial(n) = n * factorial(n-1)

'n이 0 혹은 1 일 때'와 같이 종료 조건을 찾을 수 있다.

재귀 함수 내에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료되도록 if문을 이용하여 꼭 종료 조건을 구현해주어야 한다.