재귀(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 == 1return 1
  • 재귀 호출: n * factorial(n - 1)
  • 실행 시 5 4 3 2 1 = 120 계산

3. 피보나치 수열 예제

  • 기저 조건: n == 00, n == 11
  • 재귀 호출: 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)

```

결론

  • 기저 조건을 정확히 설정하는 것이 재귀의 핵심
  • 팩토리얼은 단순한 재귀, 피보나치는 중복 계산으로 인한 비효율 주의
  • 이터레이션 대비 재귀는 메모리 사용량이 높을 수 있으므로, 단순한 문제에만 활용할 것