개념 정리
함수와 재귀 알고리즘
단원 개요
함수의 모듈화와 콜 스택(Call Stack) 메모리 프레임, 변수 스코프(지역/전역), 자기 자신을 호출하는 재귀 함수(Recursion)와 메모이제이션 최적화를 학습합니다.필수 키워드:콜 스택(Call Stack)스택 프레임매개변수(Parameters)지역 변수(Local Variables)복귀 주소(Return Address)지역 변수(Local)전역 변수(Global)순수 함수(Pure Function)재귀(Recursion)자기 자신을 다시 호출
1
함수 호출의 내부 메커니즘: 스택 프레임(Stack Frame)과 스코프
•
스택 프레임 (Stack Frame / Activation Record):
•
프로그램에서 함수가 호출될 때마다 운영체제는 메모리의 콜 스택(Call Stack) 영역에 해당 함수만을 위한 독립된 작업 공간인 스택 프레임을 생성(Push)합니다.
•
스택 프레임 내부에는 ① 매개변수(Parameters) ② 지역 변수(Local Variables) ③ 함수가 끝난 뒤 돌아갈 복귀 주소(Return Address)가 저장됩니다.
•
함수가
return 문을 만나 실행을 마치면 해당 스택 프레임은 메모리에서 즉시 소멸(Pop)되고 CPU는 복귀 주소로 돌아갑니다.•
변수의 유효 범위 (Scope - LEGB 규칙):
•
함수 내부에서 선언된 지역 변수(Local)는 그 함수의 스택 프레임 안에만 존재하므로 함수 밖에서 접근할 수 없으며, 다른 함수의 동명 변수와도 완전히 격리됩니다.
•
함수 밖에서 선언된 전역 변수(Global)는 프로그램 전체에서 읽을 수 있지만, 무분별한 전역 변수 수정은 디버깅과 멀티스레드 안정성을 해치므로 매개변수와 반환값(
return)을 통해 데이터를 주고받는 순수 함수(Pure Function) 설계가 권장됩니다.핵심 원리
함수에서 print()는 화면에 글자만 출력할 뿐 함수 외부로 값을 돌려주지 않습니다(반환값은 None). 계산 결과를 호출자에게 전달하여 다음 연산에 재사용하려면 반드시 return 결과값을 명시해야 합니다.2
재귀 함수(Recursion)의 구조와 2대 필수 구성 요소
재귀(Recursion)란 함수가 자신의 내부에서 자기 자신을 다시 호출하여 큰 문제를 동일한 형태의 더 작은 부분 문제(Subproblem)로 쪼개어 해결하는 기법입니다. 모든 올바른 재귀 함수는 반드시 다음 두 요소를 갖추어야 합니다:
1
기저 조건 (Base Case / 종료 조건):
•
문제를 더 이상 쪼갤 필요가 없는 가장 작은 크기의 문제일 때, 재귀 호출을 멈추고 즉시 결과값을 반환하는 탈출구입니다.
•
기저 조건이 없거나 도달하지 못하면 콜 스택에 스택 프레임이 무한히 쌓이다가 메모리가 고갈되는 스택 오버플로우(
RecursionError / StackOverflowError)로 프로그램이 강제 종료됩니다!2
재귀 단계 (Recursive Step / 유도 단계):
•
문제의 입력 크기를 기저 조건을 향해 점점 줄여가며( 또는 ) 자기 자신을 호출하는 점화식 단계입니다.
•
예: 팩토리얼 (기저 조건: ), 유클리드 호제법 최대공약수 (기저 조건: 일 때 ).
풀이
1) 1차 호출: gcd(48, 18)
•
b(18) != 0이므로
48 % 18 = 12를 계산하여 gcd(18, 12)를 재귀 호출합니다.2) 2차 호출: gcd(18, 12)
•
b(12) != 0이므로
18 % 12 = 6을 계산하여 gcd(12, 6)을 재귀 호출합니다.3) 3차 호출: gcd(12, 6)
•
b(6) != 0이므로
12 % 6 = 0을 계산하여 gcd(6, 0)을 재귀 호출합니다.4) 4차 호출 (기저 조건 도달!): gcd(6, 0)
•
드디어 기저 조건
b == 0이 참이 되어 재귀를 멈추고 a 값인 6을 반환합니다!5) 콜 스택 역순 복귀: gcd(6,0) → 6 ➔ gcd(12,6) → 6 ➔ gcd(18,12) → 6 ➔ gcd(48,18) → 6. 최종 최대공약수는 6입니다.
3
재귀의 중복 연산 함정과 메모이제이션(Memoization / DP)
•
단순 재귀 피보나치의 비극 ():
•
피보나치 수열 를 단순 재귀로 구현하면, 를 구하기 위해 을 2번, 를 3번 계산하는 등 이미 계산했던 똑같은 부분 문제를 수억 번 중복 호출하여 시간 복잡도가 지수 시간 으로 폭발합니다 (만 되어도 수 초 이상 소요).
•
메모이제이션 (Memoization)과 동적 계획법 (Dynamic Programming):
•
한 번 계산한 의 결과값을 배열이나 해시 테이블(
memo)에 저장(캐싱)해 두고, 같은 호출이 다시 들어오면 재귀를 타지 않고 저장된 값을 에 즉시 꺼내 쓰는 기법입니다.•
메모이제이션을 적용하는 순간 중복 호출이 완전히 사라져 시간 복잡도가 으로 드라마틱하게 단축됩니다!
•
하노이의 탑 (Tower of Hanoi):
•
원판 개를 옮기는 최소 이동 횟수 점화식은 이며 일반항은 회입니다 (재귀로만 우아하게 풀리는 대표적 분할 정복 문제).
학습 도움말
파이썬에서는 재귀 함수 바로 위에 @functools.lru_cache(maxsize=None) 또는 @functools.cache 데코레이터 한 줄만 붙여주면, 코드를 수정하지 않고도 자동으로 메모이제이션(Top-Down DP)이 적용되어 O(2^N) 재귀가 O(N)으로 최적화됩니다!핵심 요약
- ✓함수 호출 시 콜 스택에 지역 변수와 복귀 주소를 담은 스택 프레임이 Push되고, 함수 종료(return) 시 Pop되어 사라진다.
- ✓재귀 함수는 무한 호출과 스택 오버플로우를 방지하는 기저 조건(Base Case)과 문제를 축소하는 재귀 단계로 구성된다.
- ✓유클리드 호제법 gcd(a, b) = gcd(b, a % b)와 하노이의 탑(2^N - 1회 이동)은 대표적인 재귀 알고리즘이다.
- ✓중복 부분 문제가 발생하는 재귀(피보나치 등)는 메모이제이션(Memoization)을 통해 O(2^N)을 O(N)으로 최적화할 수 있다.