재귀 (순환)
재귀란 주어진 문제를 해결하기 위해 자신을 다시 호출하는 프로그래밍 기법
분할정복 > 재귀 - 기술면접
피보나치, 이항계수, 이진 트리 알고리즘 등등
**
재귀함수의 핵심 요소 두 가지
1. 종료 조건 (기본 케이스 - Base case)
- 재귀 함수가 종료되는 조건이 반드시 필요하다.
2. 문제 축소(재귀 케이스 - Recursive case)
- 재귀 함수는 큰 문제를 반드시 작은 문제로 축소시켜야한다.
재귀 활용
- 트리와 그래프 순회
- 분할 정복 알고리즘
- 동적 프로그래밍
- 백트래킹 알고리즘
직접 재귀와 간접재귀
직접 재귀 - 함수가 직접 자기 자신을 호출
간접 재귀 - 함수 A가 함수 B를 호출하고, B가 다시 A를 호출하는 형태
장점
- 코드가 간결해지고 이해하기 쉬움
- 일부 알고리즘을 자연스럽게 표현 가능
- 문제를 더 작은 하위 문제로 나누어 해결하는 방식이 직관적
단점
- 메모리 사용량이 증가할 수 있음(각 재귀 호출마다 스택 프레임 생성)
- 깊은 재귀의 경우 스택 오버플로우 발생 가능
- 때로는 반복문보다 성능이 떨어질 수 있음
재귀와 반복의 관계
반복을 사용하게 되면 지나치게 복잡해지는 문제들이 존재
이런 경우 재귀가 좋은 해결책이 될 수 있다.
**
모든 재귀는 반복으로 표현가능
모든 반복은 재귀로 표현가능
즉, 둘 다 이론적으로는 가능
// 재귀
def fib(n) :
if n <= 1 "
return n
else :
return fib(n-1) + fib(n-2)
// 반복문
def fib(n) :
if n <= 1 :
return n
prev = 0
curr = 1
for _ in range(2, n + 1 ) :
next = prev + curr
prev = curr
curr = next
return curr
재귀와 비교했을 때 반복의 장단점
장점
메모리 효율성 - 스택 오버플로우 위험이 없음
재귀보다 실행 속도 빠름
제어 흐름이 더 직관적
단점
코드 복잡성
가독성이 떨어짐
구현이 비교적 어려움
수학적 귀납법이나 분할 정복과 같은 개념을 직접적으로 표현하기 어려움
꼬리 재귀
재귀 호출 끝에서 이루어지는 재귀를 꼬리 재귀라고 한다.
꼬리 재귀 조건
1. 재귀 호출이 함수의 마지막 연산이어야 함
2. 재귀 호출의 결과가 직접 반환되어야 함
3. 재귀 호출 이후에 추가적인 연산이 없어야 함
** 꼬리 재귀 장점
컴파일러가 최적화할 수 있다.
스택 프레임을 재사용할 수 있어 메모리 사용이 효율적
// 꼬리재귀 예시
def fib_tail(n, a=0, b=1) "
if n == 0:
return a
return fib_tail(n-1, b, a+b)
// 꼬리재귀 아님 - 리턴 전에 + 연산을 수행하기 때문
def fib(n) :
if n <= 1 :
return n
return fib(n-1) + fib(n-2)
꼬리 재귀 최적화
재귀 함수 호출 시 호출 스택의 사용을 최적화하는 기법
재귀함수가 호출될 때마다 스택 프레임이 생성되며, 이는 메모리 사용량 증가와 스택 오버플로우의 원인이 됨
꼬리 재귀 최적화는 재귀 함수의 마지막 연산만 호출 스택에 남겨두고, 나머지를 제거한다.
이를 통해 함수가 반환될 때 호출 스택을 재사용할 수 있다.
**
꼬리 재귀가 마지막 연산이므로 스택에 함수 상태를 유지할 필요가 없음
- 단순 리턴만 하면 되므로 함수를 유지할 필요가 없음
**
프로그래머는 재귀 함수를 꼬리재귀로 만들면 그것이 꼬리 재귀 최적화
- 컴파일러가 자동으로 최적화하기 때문
**
꼬리 재귀는 반복문과 유사한 효율성을 갖는다.
장점
스택 사용량 감소
무한 재귀 가능
재귀의 가독성과 반복문의 효율성 결합
단점
모든 프로그래밍 언어가 꼬리 재귀 최적화를 지원하지 않음
코드 복잡성이 증가할 수 있다.
가독성이 떨어진다.
디버깅이 어려워진다.