재귀(Recursion)란 무엇인가?
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
기초 개념
대상자
- 초보 프로그래머 및 알고리즘 학습자
- 난이도: 중간 (재귀 호출, 기저 조건 이해 필요)
핵심 요약
- 재귀는 함수가 자신을 호출하여 문제를 작은 부분으로 나누어 해결하는 기법
- 기저 조건(Base Case)이 없으면
RecursionError
발생 - 팩토리얼과 피보나치 수열이 재귀의 대표적 예제
factorial(n)
은n * factorial(n-1)
로 계산,fibonacci(n)
은fibonacci(n-1) + fibonacci(n-2)
로 계산
섹션별 세부 요약
1. 재귀의 기본 구조
- 함수가 자신을 호출하는 조건과 기저 조건을 명시해야 함
- 예시:
```python
def function_name():
if condition:
return something
else:
return function_name()
```
- 기저 조건이 없으면 무한 재귀로 프로그램 종료
2. 팩토리얼 예제
- 기저 조건:
n == 0 or n == 1
→return 1
- 재귀 호출:
n * factorial(n - 1)
- 실행 시
5 4 3 2 1 = 120
계산
3. 피보나치 수열 예제
- 기저 조건:
n == 0
→0
,n == 1
→1
- 재귀 호출:
fibonacci(n-1) + fibonacci(n-2)
fibonacci(7)
출력:0 1 1 2 3 5 8
4. 미니 프로젝트: 팩토리얼 & 피보나치 계산기
- 사용자 입력을 받아 계산 수행
- 코드 예시:
```python
def factorial(n):
return 1 if n <= 1 else n * factorial(n - 1)
def fibonacci(n):
return n if n <= 1 else fibonacci(n-1) + fibonacci(n-2)
```
결론
- 기저 조건을 정확히 설정하는 것이 재귀의 핵심
- 팩토리얼은 단순한 재귀, 피보나치는 중복 계산으로 인한 비효율 주의
- 이터레이션 대비 재귀는 메모리 사용량이 높을 수 있으므로, 단순한 문제에만 활용할 것