재귀 함수(Recursive Function)란?

재귀 함수란?

재귀 함수(Recursive Function)는 자기 자신을 다시 호출하여 문제를 해결하는 함수입니다. 재귀는 문제를 작은 부분으로 쪼개어 해결하는 방법으로, 주로 반복적인 작업을 수행할 때 유용합니다.

재귀 함수의 기본 구조

재귀 함수는 일반적으로 두 가지 부분으로 구성됩니다:

1. 기저 조건(Base Case): 재귀 호출을 멈추기 위한 조건. 기저 조건을 만족하면 더 이상 재귀 호출을 하지 않고 함수가 종료됩니다.
2. 재귀 호출(Recursive Call): 함수가 자기 자신을 다시 호출하는 부분. 이때, 문제의 크기를 줄여서 호출합니다.

def recursive_function(params):
   if base_case_condition: # 특정 조건이 되면 종료해야해요!
       return result
   else:
       return recursive_function(modified_params) # 함수안에 다시 자신을 호출하는 함수가 존재해요!

재귀 함수의 예

가장 흔한 예로 팩토리얼(Factorial) 계산을 들 수 있습니다. 

팩토리얼은 양의 정수 n에 대해, 1부터 n까지의 모든 정수를 곱한 결과를 의미합니다. 

예를 들어, 5! (5 팩토리얼)은 5 * 4 * 3 * 2 * 1 = 120입니다.

팩토리얼의 재귀 함수

def factorial(n):
   if n == 1:  # 기저 조건: n이 1이면 1을 반환
       return 1
   else:
       return n * factorial(n - 1)  # 재귀 호출

# 예시
print(factorial(5))  # 출력: 120

재귀 함수의 작동 방식

재귀 함수의 작동 방식을 이해하기 위해, 함수 호출의 스택 구조를 생각하면 좋습니다. 함수가 호출될 때마다 스택에 쌓이고, 기저 조건에 도달하면 스택에서 하나씩 제거되면서 결과를 반환합니다.

예를 들어, factorial(5) 함수 호출의 과정은 다음과 같습니다:

factorial(5)
 -> 5 * factorial(4)
       -> 4 * factorial(3)
             -> 3 * factorial(2)
                   -> 2 * factorial(1)
                         -> 1 (기저 조건에 도달)

각 호출은 스택에 쌓이고, factorial(1)이 반환되면 스택이 하나씩 제거되며 결과를 반환합니다:

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

재귀 함수의 장단점

장점

• 단순성: 복잡한 문제를 간결하게 표현할 수 있습니다.
• 자연스러운 표현: 분할 정복 알고리즘과 같은 문제에 자연스럽게 적용됩니다.

단점

• 성능 문제: 함수 호출이 많아지면 호출 스택이 커져서 메모리를 많이 사용하게 됩니다.
• 무한 루프 위험: 기저 조건을 잘못 설정하면 무한 루프에 빠질 수 있습니다.

재귀 함수의 응용

1. 피보나치 수열: 피보나치 수열의 n번째 값을 재귀적으로 계산할 수 있습니다.
2. 하노이 탑: 하노이 탑 문제는 재귀를 사용하여 간단히 해결할 수 있습니다.
3. 정렬 알고리즘: 퀵 정렬과 병합 정렬 같은 정렬 알고리즘은 재귀를 사용하여 구현됩니다.
4. 트리 탐색: 이진 트리나 그래프의 깊이 우선 탐색(DFS)에서 재귀가 자주 사용됩니다.

한번 코드로 활용해볼까요?

피보나치 수열의 재귀 함수

def fibonacci(n):
   if n == 0:
       return 0
   elif n == 1:
       return 1
   else:
       return fibonacci(n - 1) + fibonacci(n - 2)

# 예시
print(fibonacci(5))  # 출력: 5 (0, 1, 1, 2, 3, 5)

요약

• 재귀 함수는 자기 자신을 다시 호출하는 함수입니다.
• 기저 조건과 재귀 호출이 기본 구조입니다.
• 재귀 함수는 복잡한 문제를 간결하게 표현할 수 있지만, 성능 문제와 무한 루프의 위험이 있습니다.
• 다양한 알고리즘과 문제 해결에 응용될 수 있습니다.