재귀 함수(Recursive Function)

재귀 함수(Recursive Function)이란?

재귀 함수는 함수 내에서 자기 자신을 다시 호출하는 함수를 의미합니다. 이를 통해 반복적인 작업을 수행할 수 있습니다.

재귀 함수의 구조

def 재귀함수():
    if 종료_조건:
        return 결과
    ...
    재귀함수()
    ...

예

팩토리얼은 재귀 함수의 대표적인 예시입니다.

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

factorial(5)를 호출한다고 가정하면, 아래와 같은 과정을 거치게 됩니다.

---

1. 첫 번째 호출: factorial(5)가 호출됩니다.
   • n = 5이므로, 5 * factorial(4)를 반환해야 합니다.
   • factorial(4)를 호출하기 위해 다음 단계로 넘어갑니다.
2. 두 번째 호출: factorial(4)가 호출됩니다.
   • n = 4이므로, 4 * factorial(3)를 반환해야 합니다.
   • factorial(3)를 호출하기 위해 다음 단계로 넘어갑니다.
3. 세 번째 호출: factorial(3)가 호출됩니다.
   • n = 3이므로, 3 * factorial(2)를 반환해야 합니다.
   • factorial(2)를 호출하기 위해 다음 단계로 넘어갑니다.
4. 네 번째 호출: factorial(2)가 호출됩니다.
   • n = 2이므로, 2 * factorial(1)를 반환해야 합니다.
   • factorial(1)를 호출하기 위해 다음 단계로 넘어갑니다.
5. 다섯 번째 호출: factorial(1)이 호출됩니다.
   • n = 1이므로, 1을 반환합니다.

각 단계에서 반환된 값을 거꾸로 계산하면 아래와 같습니다.

1. factorial(1) = 1
2. factorial(2) = 2 * 1 = 2
3. factorial(3) = 3 * 2 = 6
4. factorial(4) = 4 * 6 = 24
5. factorial(5) = 5 * 24 = 120

---

장단점

장점

1. 코드의 간결성: 재귀 함수를 사용하면 복잡한 알고리즘도 간결하게 표현할 수 있습니다.
2. 수학적 정의와 가깝다: 재귀적인 수학적 정의를 바로 코드로 옮길 수 있어 이해하기 쉽습니다.

   단점

3. 메모리 사용: 각 함수 호출마다 스택 메모리에 정보가 저장되므로 메모리 사용이 증가할 수 있습니다.
   -> 글 하단의 python에서의 재귀 호출의 깊이 제한 참고
4. 속도: 일반적인 반복문에 비해 함수 호출 오버헤드로 인해 속도가 느릴 수 있습니다.
   -> 글 하단의 함수 호출 오버헤드 참고

참고

python에서의 재귀 호출의 깊이 제한

python에서는 재귀 호출의 깊이에 제한을 두어 메모리의 오버플로우를 방지합니다. 이 제한은 시스템에 따라 다르나, 기본적으로는 1000번의 재귀 호출이 제한됩니다.

만약 이 제한을 변경하고 싶다면, sys 모듈의 setrecursionlimit함수를 사용해 변경할 수 있습니다.

import sys

sys.setrecursionlimit(2000)

이러면 최대 재귀 깊이를 2000으로 수정할 수 있습니다.

함수 호출 오버헤드란

함수 호출 오버헤드는 함수를 호출할 때 발생하는 추가적인 작업으로 인해 소요되는 시간과 리소스를 말합니다. 특히 재귀 함수와 같이 함수 호출이 연쇄적으로 발생하는 경우, 함수 호출 오버헤드는 성능에 영향을 미칠 수 있습니다.