[문법] 재귀 함수와 제한

 

 💡 재귀함수란?

재귀 함수란 자신을 호출하는 함수이며 해당 프로세스를 함수 재귀라고 한다.

이러한 재귀 함수는 자신의 로직을 내부적으로 반복하다 일정 조건이 만족되면 함수를 이탈해 결과를 도출한다.

# 재귀 함수 예시 코드 (ex. 팩토리얼)
def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return (n * fact(n - 1))
a = 6
print("Factorial of", a, "=", fact(a))

 

 

 

 

 ▪️ 재귀 호출의 제한

재귀 함수의 경우 함수가 자신을 호출 할 때마다 중간 값을 저장하기위한 메모리가 필요하다.

따라서 일반적인 비 재귀 함수보다 훨씬 많은 메모리와 시간을 소비한다.

이 때문에 파이썬엔 재귀 호출의 제한이 있는데 이는 python3을 기준으로 1000회로 설정되어 있으며, 버전에 따라 다를 수 있으므로 정확한 재귀 호출의 제한은 아래의 코드를 통해 확인 가능하다.

import sys
print(sys.getrecursionlimit())

이때 재귀 호출 제한을 초과할 경우 RecursionError가 발생한다.

 

 

 

 

 ▪️ 재귀 호출 제한의 제거

파이썬의 재귀 호출의 제한 설정의 경우, 아래의 코드를 통해 변경이 가능하다. 

import sys
sys.setrecursionlimit(5000)

 

 

 

 

 ▪️ 재귀의 장점 vs 단점

장점	단점
- 문제를 쉽게 해결할 수 있게 하위 문제로 나눌 수 있다.  - 코드가 깔끔해져 가독성이 좋아진다.	- 때로는 재귀의 논리가 더 복잡할 수 있다. - 하위 문제를 해결하기에 재귀가 오히려 더 많은 시간이 걸리므로 다소 비효율적일 수 있다.

👉 TIP : 보통 코딩테스트의 경우, 재귀를 사용하면 시간/메모리 초과가 발생하기에 권장 X.