함께 배우는 수업 · 컴퓨터/정보

함수와 재귀 알고리즘

함수의 모듈화와 콜 스택(Call Stack) 메모리 프레임, 변수 스코프(지역/전역), 자기 자신을 호출하는 재귀 함수(Recursion)와 메모이제이션 최적화를 학습합니다.

이 수업에서 해 볼 일

  • 함수의 반환값과 재귀의 종료 조건을 추적한다

먼저 알면 좋은 것: 스택(Stack, LIFO) 자료구조의 Push/Pop 원리 · 수학적 귀납법과 점화식(예: $a_n = a_{n-1} + a_{n-2}$) · 조건 분기문(if-else)과 함수의 반환값(return)

오늘의 목표

가입 없이 시작할 수 있어요. 설명을 읽고, 함께 연습한 뒤, 처음 보는 문제에서 직접 확인합니다.

판단 과정과 비교 사례

함수 호출은 인수를 받아 지역 실행 환경에서 계산하고 반환값을 호출 위치로 돌려준다. 화면에 출력하는 일과 값을 반환하는 일은 구분해야 한다.재귀를 읽을 때는 현재 호출의 남은 계산을 잠시 보류하고 더 작은 호출을 따라간다. 예를 들어 g(2)=2+g(1), g(1)=1+g(0)이라면 기저값 g(0)을 정한 뒤 거꾸로 합친다.재귀에는 도달 가능한 종료 조건과 그쪽으로 진행하는 변화가 모두 필요하다. 같은 하위 문제를 반복 계산할 때는 결과를 저장해 재사용하는 메모이제이션을 검토한다.

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 / 유도 단계): - 문제의 입력 크기를 기저 조건을 향해 점점 줄여가며(N→N−1N \rightarrow N-1 또는 N/2N/2) 자기 자신을 호출하는 점화식 단계입니다. - 예: 팩토리얼 N!=N×(N−1)!N! = N \times (N-1)! (기저 조건: 0!=10! = 1), 유클리드 호제법 최대공약수 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b) = \gcd(b, a \bmod b) (기저 조건: b=0b = 0일 때 aa).

예제로 살펴보기

유클리드 호제법을 이용한 재귀 함수 def gcd(a, b): return a if b == 0 else gcd(b, a % b)에 대해 gcd(48, 18)을 호출했을 때 콜 스택에서 일어나는 재귀 호출 과정과 최종 반환값을 단계별로 추적하시오.
  1. 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입니다.
확인: 함수 호출 시 콜 스택에 지역 변수와 복귀 주소를 담은 스택 프레임이 Push되고, 함수 종료(return) 시 Pop되어 사라진다.

3. 재귀의 중복 연산 함정과 메모이제이션(Memoization / DP)

- 단순 재귀 피보나치의 비극 (O(2N)O(2^N)): - 피보나치 수열 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)를 단순 재귀로 구현하면, F(5)F(5)를 구하기 위해 F(3)F(3)을 2번, F(2)F(2)를 3번 계산하는 등 이미 계산했던 똑같은 부분 문제를 수억 번 중복 호출하여 시간 복잡도가 지수 시간 O(2N)O(2^N)으로 폭발합니다 (n=40n=40만 되어도 수 초 이상 소요). - 메모이제이션 (Memoization)과 동적 계획법 (Dynamic Programming): - 한 번 계산한 F(k)F(k)의 결과값을 배열이나 해시 테이블(memo)에 저장(캐싱)해 두고, 같은 호출이 다시 들어오면 재귀를 타지 않고 저장된 값을 O(1)O(1)에 즉시 꺼내 쓰는 기법입니다. - 메모이제이션을 적용하는 순간 중복 호출이 완전히 사라져 시간 복잡도가 O(2N)→O(N)O(2^N) \rightarrow O(N)으로 드라마틱하게 단축됩니다! - 하노이의 탑 (Tower of Hanoi): - 원판 NN개를 옮기는 최소 이동 횟수 점화식은 T(N)=2T(N−1)+1T(N) = 2T(N-1) + 1이며 일반항은 2N−12^N - 1회입니다 (재귀로만 우아하게 풀리는 대표적 분할 정복 문제).파이썬에서는 재귀 함수 바로 위에 @functools.lru_cache(maxsize=None) 또는 @functools.cache 데코레이터 한 줄만 붙여주면, 코드를 수정하지 않고도 자동으로 메모이제이션(Top-Down DP)이 적용되어 O(2^N) 재귀가 O(N)으로 최적화됩니다!

참고 근거와 확인 범위

설명·예제·문제 구성 및 오류 수정 책임: 프리런. 위 자료는 표시한 주제를 확인하거나 더 읽기 위한 근거이며, 외부 기관의 공식 수업이나 감수본을 뜻하지 않습니다.

참고 자료 연결 점검: 2026-11-02. 제작 방식·검수 범위와 수정 기록에서 확인 범위를 볼 수 있습니다. 오류는 상단의 의견 보내기 또는 contact@freelearn.io로 알려 주세요.

이 단원의 개념서 읽기 →