- Level: Beginner
- Prerequisites: Programming/Variables-and-Types.md, Programming/Control-Flow.md
- Status: Draft
- Reviewed-by: -
- Depth: Deep-dive (자기완결)
함수는 입력을 받아 정해진 작업을 수행하고 결과를 반환하는 코드 묶음이다. 재귀는 함수가 자기 자신을 호출해서 문제를 더 작은 문제로 나누는 기법이다.
함수는 프로그램의 이름 붙은 부품이다. 같은 코드를 반복해서 쓰지 않고, 의미 있는 단위로 나누며, 테스트하기 쉬운 경계를 만든다.
재귀는 "큰 문제를 같은 형태의 작은 문제로 줄일 수 있을 때" 자연스럽다. 예를 들어 리스트의 합은 첫 원소와 나머지 리스트의 합으로 나눌 수 있다.
flowchart TD
CALL["factorial(3)"] --> C2["3 * factorial(2)"]
C2 --> C1["2 * factorial(1)"]
C1 --> C0["1 * factorial(0)"]
C0 --> BASE["1"]
BASE --> R1["1 * 1"]
R1 --> R2["2 * 1"]
R2 --> R3["3 * 2 = 6"]
좋은 함수는 보통 다음 성질을 가진다.
| 성질 | 의미 |
|---|---|
| 단일 책임 | 하나의 분명한 일을 한다 |
| 명확한 입력 | 필요한 값을 매개변수로 받는다 |
| 명확한 출력 | 결과를 반환하거나 부작용을 분명히 한다 |
| 작은 범위 | 읽고 테스트하기 쉬운 크기다 |
재귀 함수에는 두 부분이 필요하다.
- 기본 조건: 더 이상 자기 자신을 호출하지 않고 끝나는 경우
- 재귀 단계: 문제를 더 작은 같은 형태의 문제로 줄이는 경우
기본 조건이 없거나 문제 크기가 줄지 않으면 재귀는 끝나지 않는다.
함수를 호출하면 매개변수, 지역 변수, 돌아갈 위치가 호출 프레임에 저장된다. 재귀는 이 프레임이 여러 겹 쌓인다. 그래서 재귀의 공간 복잡도는 보통 최대 재귀 깊이와 같다. 꼬리 재귀 최적화를 지원하는 언어도 있지만 Python처럼 지원하지 않는 언어에서는 깊은 재귀가 RecursionError나 스택 오버플로로 이어질 수 있다.
함수 설계에서 계산 결과를 return으로 돌려주는지, 외부 상태를 수정하는지 구분한다. 같은 입력에 같은 값을 반환하는 함수는 테스트와 조합이 쉽다. 파일 쓰기, 네트워크 호출, 전역 변수 변경 같은 부작용은 필요하지만 경계를 분명히 해야 한다.
함수 예시:
def average(values):
if len(values) == 0:
return 0
return sum(values) / len(values)
print(average([90, 85, 100]))재귀 예시:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120리스트 합도 재귀로 표현할 수 있다.
def recursive_sum(values):
if len(values) == 0:
return 0
return values[0] + recursive_sum(values[1:])다만 위 구현은 슬라이싱 때문에 매 호출마다 새 리스트를 만들 수 있다. 실제 코드에서는 인덱스를 넘기거나 반복문을 쓰는 편이 더 효율적일 수 있다.
슬라이싱 없이 재귀 합을 쓰면 비용이 달라진다.
def recursive_sum_index(values, i=0):
if i == len(values):
return 0
return values[i] + recursive_sum_index(values, i + 1)values[1:]는 매번 새 리스트를 만들 수 있지만, 인덱스 i만 넘기면 같은 배열을 공유한다.
| 함수 | 시간 | 공간 |
|---|---|---|
average(values) |
O(n) | O(1) |
factorial(n) |
O(n) | O(n) |
| 슬라이싱을 쓰는 재귀 합 | O(n^2) | O(n^2) |
| 인덱스를 쓰는 재귀 합 | O(n) | O(n) |
재귀의 공간 복잡도에는 호출 스택이 포함된다.
워크드 예제: recursive_sum_index([4, 5, 6])은 깊이 4의 호출을 만든다. i=0,1,2에서 값을 더하고 i=3에서 0을 반환한다. 시간은 원소 3개를 한 번씩 보므로 O(n), 스택은 깊이 n+1이므로 O(n)이다.
- 중복 로직 제거
- 입력 검증과 계산 로직 분리
- 트리와 그래프 탐색
- 분할 정복 알고리즘
- 수학적 정의를 코드로 옮기기
- 함수가 짧다고 항상 좋은 것은 아니다. 의미 있는 단위로 나뉘어야 한다.
- 재귀가 반복문보다 항상 우아하거나 빠른 것은 아니다.
- 반환값과 출력은 다르다.
print는 화면에 보여 주는 부작용이고,return은 호출한 코드에 값을 돌려준다. - 기본 조건이 있어도 재귀 단계에서 문제 크기가 줄지 않으면 종료되지 않는다.
- 재귀 예제로 factorial과 Fibonacci가 자주 나오지만, 실무에서는 트리, 파일 시스템, 파서처럼 "안에 같은 구조가 다시 들어 있는" 문제에서 특히 자연스럽다.
- Python은 기본 재귀 깊이에 제한이 있다. 재귀가 너무 깊어질 수 있는 문제는 반복문이나 명시적 스택으로 바꾸는 편이 안전하다.
- Python의 기본 인자 값은 함수가 호출될 때마다 새로 만들어지는 것이 아니라 함수가 정의될 때 한 번 만들어진다. 그래서
def f(x=[]): ...같은 코드는 의도치 않게 리스트를 공유할 수 있다. - Java는 객체를 넘길 때도 "참조값을 값으로 복사"한다. 그래서 Java를 pass-by-reference라고 부르면 엄밀히는 틀린 설명이다.
- 숫자 목록을 받아 최댓값을 반환하는 함수를 작성하라.
factorial을 반복문 버전과 재귀 버전으로 각각 작성하라.- 문자열이 팰린드롬인지 검사하는 재귀 함수를 작성하라.