이번 포스팅에서는 Python 재귀 (Recursion) 특징에 대해서 알아 보겠습니다.
Python 프로그래밍에서 함수가 자신을 호출하는 것을 재귀(Recursion)라고 합니다. 재귀는 특정 문제를 더 작은 하위 문제로 나누어서 해결책을 얻습니다.
Python 재귀 (Recursion) 란
재귀의 기본은 문제가 동일한 유형의 더 작은 문제로 변환될 수 있다는 것입니다. 재귀는 자체 내에서 함수를 다시 호출하는 것입니다.
Python에서는 함수가 다른 함수를 호출할 수 있습니다. 물론, 함수가 자신을 호출하는 것도 가능합니다. 이러한 유형의 구성을 재귀 함수라고 합니다.
기본 재귀 규칙
기본 사례 정의
재귀가 무한 루프로 진행되는 것을 방지하려면 기본 사례를 결정해야 합니다. 기본 사례는 재귀가 끝나는 것을 보장합니다.
함수를 더 작은 문제로 나누기
재귀는 원래 문제의 더 작은 버전으로 변환하여 작동합니다. 여기에는 자신을 호출하는 함수가 포함됩니다.
예제1: 피보나치 수열
피보나치 수열은 각 숫자가 그 앞의 두 숫자의 합인 수열입니다. 피보나치 수열을 계산하는 재귀 예제는 아래와 같습니다.
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)예제2: 팩토리얼 계산
팩토리얼은 1부터 해당 숫자까지의 모든 정수를 곱한 숫자를 의미합니다. 예를 들어, 6 팩토리얼은 1*2*3*4*5*6 = 720입니다.
def factorial(x):
if x == 1:
return 1
else:
return (x * factorial(x-1))
num = 3
print(num, "팩토리얼은", factorial(num), "입니다.")
-------------------------------------------------------
3 팩토리얼은 6 입니다.
위의 예에서 factorial()은 자신을 호출하는 재귀 함수입니다. 양의 정수로 이 함수를 호출하면 숫자를 줄여서 자신을 재귀적으로 호출합니다. 각 함수는 숫자가 1과 같아질 때까지 아래 숫자의 factorial과 숫자를 곱합니다.
숫자가 1로 줄어들면 재귀가 종료됩니다. 이를 기본 조건이라고 합니다. 모든 재귀 함수에는 재귀를 중지하는 기본 조건이 있어야 합니다. 그렇지 않으면 함수는 자신을 무한히 호출합니다.
Python 인터프리터는 무한 재귀를 방지하기 위해 재귀 깊이를 제한하여 스택 오버플로가 발생합니다. 기본적으로 최대 재귀 깊이는 1000입니다. 제한을 초과하면 RecursionError가 발생합니다.
재귀의 장점
더 적은 수의 코드를 사용하여 특정 문제를 해결하고 코드를 더 이해하기 쉽게 만들 수 있습니다. 또한, 재귀는 문제에 대한 솔루션을 더 작고 관리하기 쉬운 조각으로 나누어 코드를 모듈화하고 유지 관리하기 쉽게 만듭니다.
재귀의 단점
재귀는 큰 문제를 처리할 때 성능 문제를 일으킬 수 있습니다. 각 재귀 단계는 호출 프레임을 생성하므로 메모리 사용량과 처리 시간이 늘어날 수 있습니다. 재귀는 잘못 구현되거나 기본 사례가 올바르게 지정되지 않은 경우 무한 루프를 발생시켜 디버깅을 어렵게 만들 수 있습니다.
결론
재귀는 특정 문제를 해결하는 강력한 도구이지만 올바르게 사용해야 합니다. 기본 조건을 정확하게 파악하고 성능 문제에 주의하는 것이 중요합니다.
재귀를 사용하면 코드를 더 이해하기 쉽고 모듈화할 수 있지만 경우에 따라 다른 해결 방법이 더 효과적일 수도 있습니다.