기초수학재귀적 알고리즘#346

재귀적 알고리즘

Recursive Algorithms

재귀적 알고리즘은 더 작은 입력의 같은 문제를 호출하고 그 답으로 원래 답을 만드는 절차다. 0 이상의 정수에 대한 계승, 세 기둥 하노이의 탑, 피보나치 수열을 예로 기저 사례·호출과 반환·유한 종료·중복 호출을 순서도와 의사코드로 확인한다.

읽는 시간
약 8분
선수 개념
알고리즘의 표현

직관 — 작은 계산의 답을 기다린다

직관

네 개까지 곱하는 일을 맡은 사람이 세 개까지 곱한 답을 기다린다. 그 사람도 두 개까지의 답을 기다리고, 끝내 바로 답할 수 있는 가장 작은 문제에 도착한다. 이제 답을 돌려주면서 기다리던 곱셈을 거꾸로 완성한다.

재귀 호출은 같은 절차에 더 작은 문제를 맡기는 일이다. 반환은 얻은 답을 호출한 자리로 돌려주는 일이다. 알고리즘의 표현에서 배운 분기와 종료를 이용해, 호출만 내려가는 것이 아니라 답이 올라오는 과정까지 읽어 보자. 프로그램의 함수가 자기 자신을 부르는 방식이 바로 이것이며, 하노이의 탑·최대공약수·분할의 수처럼 작은 경우로 쪼개지는 문제를 짧게 표현한다.

재귀적 알고리즘은 작은 문제의 답으로 원래 문제를 해결한다

재귀적 알고리즘은 자기와 같은 문제를 더 작은 입력으로 호출해 해결하는 알고리즘이다. 바로 답할 수 있는 기저 사례와, 그 사례에 유한 번 만에 도달하도록 입력을 줄이는 규칙이 함께 필요하다.

계승 n!n!은 양의 정수 nn에 대해 1⋅2⋯n1\cdot2\cdots n이고, 0!=10!=1로 정한다. F(n)=n!F(n)=n!을 다음처럼 쓸 수 있다.

F(0)=1,F(n)=nF(n−1)(n≥1).(1)F(0)=1,\qquad F(n)=nF(n-1)\quad(n\ge1).\tag{1}
정의
기호이름원어뜻
nn입력 크기input size0 이상의 정수
n!,F(n)n!,F(n)계승, 계승 계산factorial0이면 1, 양수이면 1부터 n까지의 곱
vv반환받은 값returned value작은 문제의 답을 저장한 값
A,B,CA,B,C기둥 이름pegs하노이에서 서로 다른 세 기둥
TnT_n이동 횟수move count설명한 하노이 절차의 n개 이동 횟수

다음 의사코드의 [반환]을 만나면 현재 호출이 끝난다. 큰 문제를 호출한 곳으로 돌아가므로 모든 계산이 즉시 끝난다는 뜻은 아니다.

[정의] F(n):                 # 정수 n ≥ 0
    [조건] n = 0이면:
        [반환] 1
    v ← F(n − 1)
    [반환] n × v

그림 1의 마름모에서 0인지 먼저 확인한다. 참인 길은 바로 1을 돌려주고, 거짓인 길은 작은 호출의 결과를 받은 뒤 곱한다. IN은 입력, OUT은 현재 호출의 반환, T/F는 참/거짓이다.

계승 F의 한 호출을 나타내는 순서도다. 정수 n≥0에서 n=0이면 1을 반환하고, 그렇지 않으면 F(n−1)의 답 v를 받은 뒤 nv를 반환한다. OUT은 호출한 자리로 돌아가는 지점이다.
그림 1 계승 F의 한 호출을 나타내는 순서도다. 정수 n≥0에서 n=0이면 1을 반환하고, 그렇지 않으면 F(n−1)의 답 v를 받은 뒤 nv를 반환한다. OUT은 호출한 자리로 돌아가는 지점이다. figures/factorial_flow.py

호출 순서와 반환 순서는 어떻게 다를까?

호출은 큰 입력에서 작은 입력으로 내려가고, 반환은 가장 작은 입력부터 거꾸로 올라온다. F(4)F(4)는 F(3)F(3), F(2)F(2), F(1)F(1), F(0)F(0)을 차례로 부르고, 곱셈은 F(0)=1F(0)=1이 돌아온 뒤에야 F(1)F(1)부터 완성된다.

F(1)=1⋅1=1,F(2)=2⋅1=2,F(3)=3⋅2=6,F(4)=4⋅6=24.(2)\begin{aligned} F(1)&=1\cdot1=1,\\ F(2)&=2\cdot1=2,\\ F(3)&=3\cdot2=6,\\ F(4)&=4\cdot6=24. \end{aligned}\tag{2}

그림 2의 회색 화살표가 호출, 파란 화살표가 돌아오는 값 vv다. 각 상자는 vv를 받을 때까지 곱셈을 미뤄 둔다. 호출은 F(4)F(4)부터 F(0)F(0)까지 5번이고, 곱셈은 F(0)F(0)을 뺀 네 상자에서 한 번씩 4번이다.

F(4)를 호출하면 회색 화살표를 따라 F(0)까지 내려간 뒤, 파란 화살표를 따라 반환값 v=1, 1, 2, 6이 한 칸씩 올라오고 마지막에 24가 나온다. 상자 안의 곱셈은 아래에서 v가 돌아올 때 완성된다.
그림 2 F(4)를 호출하면 회색 화살표를 따라 F(0)까지 내려간 뒤, 파란 화살표를 따라 반환값 v=1, 1, 2, 6이 한 칸씩 올라오고 마지막에 24가 나온다. 상자 안의 곱셈은 아래에서 v가 돌아올 때 완성된다. figures/factorial_trace.py

각 호출은 자기 입력을 기억한다. F(2)F(2) 안에서 사용하는 nn은 2이고, F(4)F(4)가 기다리며 보관한 nn은 4다. 작은 호출에서 번호가 줄었다고 바깥 호출의 4까지 0으로 바뀌는 것이 아니다.

0에서의 답이 맞고, 작은 입력에서 답이 (n−1)!(n-1)!라면 반환값은 n(n−1)!=n!n(n-1)!=n!이다. 이 귀납적 구조가 정확성의 일반 이유다. 종료는 별도로, 정수 입력이 매번 1씩 줄어 정확히 0에 도달한다는 사실로 설명한다.

하노이의 탑은 어떻게 같은 문제 두 개로 나뉠까?

세 기둥에서 크기가 서로 다른 원판을 옮기자. 한 번에 맨 위 원판 하나만 옮기고, 큰 원판을 작은 원판 위에 놓지 않는다. A의 원판 n개를 C로 옮길 때 B를 보조 기둥으로 쓴다.

가장 큰 원판을 A에서 C로 옮기려면 그 위의 n−1개를 먼저 B로 옮긴다. 큰 원판 하나를 옮긴 뒤에는 B의 n−1개를 C로 옮긴다. 두 작은 문제에서 목적지와 보조 기둥의 역할이 달라진다.

[정의] H(n, A, C, B):       # n ≥ 0, A→C, 보조 B
    [조건] n = 0이면:
        [반환]              # 옮길 원판이 없음
    H(n − 1, A, B, C)
    A의 맨 위 원판을 C로 옮긴다
    H(n − 1, B, C, A)
    [반환]

그림 3은 H(3,A,C,B)H(3, A, C, B)의 호출 나무다. 상자 하나가 원판이 있는 호출 하나이고, 상자 안의 화살표는 그 호출이 직접 하는 이동이다. 왼쪽 자식 호출을 모두 마친 뒤 자기 이동, 그다음 오른쪽 자식 호출 순서로 실행되므로 상자의 가로 순서가 그대로 이동 순서가 된다.

원판 3개를 A에서 C로 옮기는 호출 나무다. 각 상자는 한 호출과 그 호출이 옮기는 가장 큰 원판의 출발→도착 기둥이며, 아래 숫자 1~7이 실제 이동 순서다. 맨 위 A→C(가장 큰 원판)는 네 번째로 움직인다.
그림 3 원판 3개를 A에서 C로 옮기는 호출 나무다. 각 상자는 한 호출과 그 호출이 옮기는 가장 큰 원판의 출발→도착 기둥이며, 아래 숫자 1~7이 실제 이동 순서다. 맨 위 A→C(가장 큰 원판)는 네 번째로 움직인다. figures/hanoi_call_tree.py

그림 3을 왼쪽부터 읽으면 A→C, A→B, C→B, A→C, B→A, B→C, A→C의 일곱 동작이다. 한 호출 아래의 두 상자는 원판 수가 같지만 출발·도착 기둥이 다르다. 이 절차의 이동 횟수는

T0=0,Tn=2Tn−1+1(n≥1).(3)T_0=0,\qquad T_n=2T_{n-1}+1\quad(n\ge1).\tag{3}

Tn+1=2(Tn−1+1)T_n+1=2(T_{n-1}+1)이므로 일차 점화식의 변형으로 Tn=2n−1T_n=2^n-1을 얻는다. 원판 3개면 23−1=72^3-1=7번이다. 수열의 귀납적 정의에서 원판 1개부터 센 hnh_n과 n≥1n\ge1에서 같은 수이고, 여기서는 원판이 없는 n=0n=0을 기저로 둔다.

원판을 한 개 줄여 호출하므로 이 절차는 유한하게 끝난다. 작은 문제의 이동이 규칙에 맞는다고 하면, 가장 큰 원판은 맨 아래에 있어 작은 원판들의 이동을 방해하지 않는다. 큰 원판을 옮기는 순간 목적지에는 작은 원판이 없으므로 전체 과정도 규칙을 지킨다. 또 2n−12^n-1번은 규칙을 지키는 방법 가운데 가장 적은 이동 횟수다.

원판 n개를 2ⁿ−1번보다 적게 옮길 수 없는 이유

원판 n개를 규칙대로 옮기는 최소 횟수를 MnM_n이라 하자. 가장 큰 원판이 A를 처음 떠나는 순간, 나머지 n−1개는 A에도 그 원판의 도착 기둥에도 있을 수 없으므로 모두 남은 한 기둥에 쌓여 있다. 그때까지는 작은 원판들만 움직였으므로 적어도 Mn−1M_{n-1}번이 필요하다.

가장 큰 원판이 마지막으로 C에 도착하는 순간에도 나머지는 모두 그 이동의 출발 기둥도 C도 아닌 기둥에 있고, 그 뒤 C 위로 모두 옮겨야 하므로 다시 적어도 Mn−1M_{n-1}번이 필요하다. 큰 원판의 이동 1번을 더하면 Mn≥2Mn−1+1M_n\ge2M_{n-1}+1이다.

M0=0=T0M_0=0=T_0에서 시작하면 Mn≥2Tn−1+1=TnM_n\ge2T_{n-1}+1=T_n이 차례로 성립한다. 설명한 절차가 정확히 TnT_n번에 해내므로 Mn=Tn=2n−1M_n=T_n=2^n-1이다.

피보나치 수열을 재귀로 계산하면 왜 같은 계산이 반복될까?

한 호출이 작은 호출 두 개를 부르고, 그 두 호출이 같은 입력을 다시 부르기 때문이다. 메모 없이 FIB(6)\mathrm{FIB}(6)을 실행하면 호출이 15번이고, 그중 9번은 이미 한 계산을 되풀이한다.

피보나치 수열은 앞의 두 항을 더해 다음 항을 만든다. 첫째 항부터 번호를 붙여 쓰면

a1=a2=1,an=an−1+an−2(n≥3).(4)a_1=a_2=1,\qquad a_n=a_{n-1}+a_{n-2}\quad(n\ge3).\tag{4}

두 칸 아래까지 내려가므로 기저 사례도 n=1n=1과 n=2n=2 두 개가 필요하다. 식 (4)를 그대로 옮긴 의사코드는 다음과 같다.

[정의] FIB(n):              # 정수 n ≥ 1
    [조건] n ≤ 2이면:
        [반환] 1
    [반환] FIB(n − 1) + FIB(n − 2)

그림 4에서 굵은 파란 원 6개는 입력 1~6을 처음 계산하는 호출이고, 회색 원 9개는 같은 입력을 다시 계산하는 호출이다. 입력 4는 2번, 입력 3은 3번, 입력 2는 5번 호출된다.

메모 없이 FIB(6)을 실행할 때의 호출 나무다. 원 안의 수는 입력 n이고, 왼쪽 호출 FIB(n−1)부터 계산한다. 굵은 파란 원 6개는 처음 계산하는 호출, 회색 원 9개는 이미 계산한 입력을 다시 계산하는 호출로 모두 15번이다.
그림 4 메모 없이 FIB(6)을 실행할 때의 호출 나무다. 원 안의 수는 입력 n이고, 왼쪽 호출 FIB(n−1)부터 계산한다. 굵은 파란 원 6개는 처음 계산하는 호출, 회색 원 9개는 이미 계산한 입력을 다시 계산하는 호출로 모두 15번이다. figures/fibonacci_call_tree.py

호출 횟수를 cnc_n이라 하면 c1=c2=1c_1=c_2=1이고, n≥3n\ge3에서 자기 호출 1번에 두 작은 호출의 횟수가 더해져 cn=cn−1+cn−2+1c_n=c_{n-1}+c_{n-2}+1이다. 양변에 1을 더하면 cn+1c_n+1이 식 (4)와 같은 규칙을 따르고 c1+1=c2+1=2c_1+1=c_2+1=2이므로 cn+1=2anc_n+1=2a_n이다.

cn=2an−1.(5)c_n=2a_n-1.\tag{5}

이미 구한 값을 표에 적어 두고 다시 필요하면 표를 읽는 방법을 메모(메모이제이션)라 한다. 아래 절차는 a3a_3부터 ana_n까지 각 값을 한 번씩만 더하므로 덧셈이 n−2n-2번이다.

[정의] FIB_MEMO(n):         # 표 memo는 비어 있는 채로 시작
    [조건] n ≤ 2이면:
        [반환] 1
    [조건] memo[n]이 있으면:
        [반환] memo[n]
    memo[n] ← FIB_MEMO(n − 1) + FIB_MEMO(n − 2)
    [반환] memo[n]
nana_n메모 없는 호출 cnc_n메모 없는 덧셈메모를 쓴 덧셈
681574
1055109548
20676513529676418

메모 없이 실행하면 n≤2n\le2인 맨 아래 호출이 모두 1을 돌려주므로, 결과 ana_n은 1을 ana_n개 더한 것이다. 그래서 덧셈은 an−1a_n-1번이다. 같은 수열을 계산해도 절차에 따라 일의 양이 크게 달라지며, 이것이 알고리즘을 비교하고 반성하는 출발점이다.

최대공약수와 분할의 수도 같은 틀의 재귀로 쓴다

교육과정은 계승·하노이의 탑·피보나치 수열 외에 최대공약수, 집합의 분할, 수의 분할을 재귀적 알고리즘의 예로 든다. 모두 입력이 줄어드는 같은 꼴의 문제를 부르고, 바로 답할 수 있는 기저 사례에서 멈춘다.

알고리즘기저 사례재귀 호출줄어드는 양
계승 F(n)F(n)n=0n=0이면 1F(n−1)F(n-1) 한 번nn
하노이 H(n,…)H(n,\ldots)n=0n=0이면 이동 없음H(n−1,…)H(n-1,\ldots) 두 번nn
피보나치 FIB(n)\mathrm{FIB}(n)n≤2n\le2이면 1FIB(n−1)\mathrm{FIB}(n-1), FIB(n−2)\mathrm{FIB}(n-2)nn
최대공약수 GCD(a,b)\mathrm{GCD}(a,b)b=0b=0이면 aaGCD(b, a mod b)\mathrm{GCD}(b,\,a\bmod b)둘째 수 bb
집합의 분할 S(n,k)S(n,k)k=1k=1 또는 k=nk=n이면 1S(n−1,k−1)S(n-1,k-1), S(n−1,k)S(n-1,k)nn

GCD(252,198)\mathrm{GCD}(252,198)은 GCD(198,54)\mathrm{GCD}(198,54), GCD(54,36)\mathrm{GCD}(54,36), GCD(36,18)\mathrm{GCD}(36,18), GCD(18,0)\mathrm{GCD}(18,0)을 차례로 부르고 18을 받는다. 받은 값을 바꾸지 않고 그대로 돌려주므로 계승과 달리 기다리는 계산이 없다. 나머지로 줄여도 답이 같은 이유는 정수 문제의 알고리즘에서 다룬다.

집합의 분할 수 S(n,k)S(n,k)는 서로 다른 nn개 원소를 비어 있지 않은 kk개 블록으로 나누는 방법의 수다. 1<k<n1<k<n에서 다음 관계를 쓴다. 두 호출은 첫째 입력이 1 줄고 둘째 입력이 1 이상 n−1n-1 이하에 머물러, 결국 기저 사례에 닿는다.

S(n,k)=S(n−1,k−1)+kS(n−1,k).(6)S(n,k)=S(n-1,k-1)+kS(n-1,k).\tag{6}

S(4,2)S(4,2)를 호출하면 S(3,1)S(3,1)과 S(3,2)S(3,2)를 부르고, S(3,2)S(3,2)는 다시 S(2,1)S(2,1)과 S(2,2)S(2,2)를 부른다. 호출은 모두 5번이다.

S(3,2)=S(2,1)+2S(2,2)=1+2⋅1=3,S(4,2)=S(3,1)+2S(3,2)=1+2⋅3=7.(7)\begin{aligned} S(3,2)&=S(2,1)+2S(2,2)=1+2\cdot1=3,\\ S(4,2)&=S(3,1)+2S(3,2)=1+2\cdot3=7. \end{aligned}\tag{7}

자연수의 분할 수 P(n,k)=P(n−1,k−1)+P(n−k,k)P(n,k)=P(n-1,k-1)+P(n-k,k)도 같은 방식이다. 다만 P(5,3)P(5,3)이 P(2,3)P(2,3)을 부르듯 k>nk>n인 입력이 생기므로, 그때 0을 돌려주는 기저 사례가 하나 더 필요하다. 그러면 P(8,3)=P(7,2)+P(5,3)=3+2=5P(8,3)=P(7,2)+P(5,3)=3+2=5다.

핵심

재귀적 알고리즘은 기저 사례와 그 사례로 다가가는 입력 감소를 명시한다. F(0)=1이고 정수 n≥1에서 F(n)=nF(n−1)이면, 작은 호출이 반환한 값에 현재 n을 곱해 계승을 구한다.

재귀적 알고리즘에 종료 조건만 쓰면 반드시 끝나나요?

아니다. 조건을 n=0n=0으로 두고 F(n+1)F(n+1)을 호출하면 양의 입력에서 0에 도달하지 못한다. 기저 사례가 있다는 것과 허용 입력이 그 사례에 도달한다는 것은 따로 확인한다.

계승의 재귀 알고리즘에 음수나 1.5 같은 수를 넣으면 어떻게 되나요?

계승의 재귀 의사코드에 음수나 1.5를 넣으면 기저 사례 n=0n=0에 닿지 못해 호출이 끝나지 않는다. −1,−2,…-1,-2,\ldots와 1.5, 0.5, −0.5,…1.5,\ 0.5,\ -0.5,\ldots는 1씩 줄어도 0을 건너뛰기 때문이다. 식 (1)의 입력을 0 이상의 정수로 정한 이유다.

재귀적 알고리즘은 반복문보다 항상 빠른가요?

아니다. 재귀는 문제의 구조를 그대로 옮기는 표현이고, 일의 양은 절차에 따라 다르다. 메모 없는 FIB(20)\mathrm{FIB}(20)은 13529번 호출하지만, 앞에서부터 두 항을 더해 가는 반복문은 덧셈 18번이면 된다.

재귀적 알고리즘에 관한 오해

  • 0을 만나면 반환값도 0이다 — 계승의 기저 반환값은 1이다. 0을 반환하면 기다리던 곱셈들의 결과가 모두 0이 된다.
  • 하노이의 두 호출은 완전히 같은 일을 반복한다 — 원판 수는 같지만 출발지·목적지·보조 기둥이 바뀐다. 그림 3에서 맨 위 호출 아래의 A→B와 B→C처럼 인수의 순서까지 읽어야 한다.
  • 기저 사례는 하나면 충분하다 — FIB에서 n=1n=1만 기저로 두면 FIB(2)\mathrm{FIB}(2)가 FIB(0)\mathrm{FIB}(0)을 부르고, 그 아래 −1,−2,…-1,-2,\ldots로 내려가 끝나지 않는다. 두 칸 아래까지 부르는 절차는 두 기저 n=1,2n=1,2가 필요하다.

직접 해보기

  1. F(5)에서 가장 깊은 호출과 반환값들을 적자. F를 총 몇 번 호출하는가?
답

가장 깊은 호출은 F(0)이며, 반환은 1, 1, 2, 6, 24, 120 순서다. 최초 F(5)까지 포함하여 F(5), F(4), F(3), F(2), F(1), F(0)의 6번 호출이다.

  1. 다음 재귀 D가 정수 n≥0에서 계산하는 것을 설명하고 D(4)를 구하자: D(0)=0, D(n)=D(n−1)+2n.
답

첫째부터 n번째까지의 짝수 2, 4, …, 2n을 더한다. D(4)=2+4+6+8=20이다. D(n)=n(n+1)을 대입하면 기저 0과 차이 2n이 모두 맞는다.

  1. 하노이 원판 4개의 전체 이동 횟수와, 가장 큰 원판을 A에서 C로 옮기기 직전까지의 이동 횟수는?
답

전체는 24−1=152^4-1=15번이다. 직전에는 작은 원판 3개를 B로 옮겼으므로 23−1=72^3-1=7번이며, 가장 큰 원판의 이동은 여덟 번째다.

  1. 계승 함수의 종료 조건을 n=1로만 바꾸고 허용 입력 n≥0을 유지하면 문제가 있는가?
답

입력 0에서 종료 조건이 거짓이므로 −1, −2로 내려가 끝나지 않는다. n=0 기저를 다시 두거나, 양의 정수만 허용하고 0의 계산을 별도로 정의해야 한다.

  1. 메모 없이 FIB(7)을 실행하면 FIB를 모두 몇 번 호출하는가? 입력 3으로는 몇 번 호출하며, 메모를 쓰면 덧셈은 몇 번인가?
답

FIB(7)은 FIB(6)과 FIB(5)를 부른다. 그림 4의 FIB(6) 나무 15번, FIB(5) 나무 2⋅5−1=92\cdot5-1=9번, 맨 위 호출 1번을 더해 25번이고, 식 (5)로도 a7=13a_7=13에서 2⋅13−1=252\cdot13-1=25다. 입력 3은 FIB(6) 나무의 3번과 FIB(5) 나무의 2번을 합쳐 5번이다. 메모를 쓰면 a3a_3부터 a7a_7까지 덧셈 5번이다.

더 읽기

  • 교육부 고시 제2022-33호 — 별책20 [12이수02-04]와 해설. 계승, 집합의 분할, 수의 분할, 피보나치 수열, 하노이의 탑, 최대공약수를 재귀적 알고리즘의 예로 든다.
  • 우리교과서 『이산 수학』 공개 원문 — 인쇄67–70쪽의 계승 의사코드, 기저 사례와 하노이의 분할. 이 글은 계승4의 반환 과정과 원판3의 실제 동작을 직접 풀었다.

영상 노트

영상 노트
  • 00:00 작은 문제의 답은 어디로 돌아올까?
  • 00:35 그림 1에서 기저 사례와 재귀 호출 나누기
  • 01:15 그림 2로 호출은 내려가고 반환은 올라오는 순서 따라가기
  • 02:00 그림 3의 호출 나무에서 하노이 이동 순서 1~7 읽기
  • 02:50 식 (3)의 이동 횟수와 2ⁿ−1이 최소인 이유
  • 03:40 그림 4에서 FIB(6)의 중복 호출 세고 식 (5)와 메모로 정리하기
  • 04:40 최대공약수와 식 (6)의 집합의 분할을 같은 틀로 정리하기

지도에서의 위치

수열의 귀납적 정의미적분알고리즘의 표현기초수학재귀적 알고리즘지금 이 페이지정수 문제의 알고리즘기초수학
선수 개념
이 페이지
다음 개념
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 독립 검수 RA1 — 핵심 요약에 허용 입력 조건을 명시함
  2. 2026-11-16 · 에이전트 초안
  3. 2026-11-17 · 전수 검수 반영 — 호출·반환 추적, 하노이 호출 나무와 최소 횟수의 이유, 피보나치 중복 호출과 메모, 최대공약수·집합의 분할 재귀 표현, 해보기 5문항 보강, 메모 표 기호와 해보기 답 문구 정리 (에이전트 수정, 그림 1→4)
  4. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림