알고리즘(Algorithm)

재귀(Recursion)

문제를 같은 모양의 더 작은 문제로 줄여 푸는 방법. 하노이의 탑⁠(Tower of Hanoi)⁠처럼, 가장 작은 경우와 '한 단계 줄이기'만 정하면 된다.

T(n) = 2\,T(n-1) + 1,\quad T(1) = 1 \quad\Longrightarrow\quad T(n) = 2^n - 1

먼저 보면 좋은 개념함수 수학적 귀납법

재귀는 문제를 같은 모양의 더 작은 문제로 바꾸어 푸는 방법입니다. 필요한 것은 두 가지뿐입니다. 더 쪼갤 필요 없이 바로 답할 수 있는 가장 작은 경우(기저 사례⁠, base case⁠)와, 큰 경우를 한 단계 작은 경우로 줄이는 규칙입니다. 나머지는 같은 규칙이 끝까지 알아서 해 줍니다. 수학적 귀납법⁠(mathematical induction)⁠을 거꾸로 쓰는 셈이라, 재귀가 옳게 동작한다는 증명도 대개 귀납법입니다.

1883년 프랑스의 수학자 에두아르 뤼카가 퍼뜨린 하노이의 탑이 가장 유명한 예입니다. 크기가 다른 원판 n장이 기둥 A에 큰 것부터 쌓여 있습니다. 한 번에 한 장씩 옮기되 작은 원판 위에 큰 원판을 올릴 수 없을 때, 전부 C로 옮기려면 어떻게 할까요? 재귀로 보면 간단합니다. 위의 n−1장을 (C를 거쳐) B로 옮기고, 가장 큰 원판을 C로 옮긴 뒤, B의 n−1장을 (A를 거쳐) C로 옮깁니다. 'n−1장 옮기기'를 어떻게 하는지는 같은 규칙이 다시 정해 줍니다.

원판 장.

원판은 한 번에 한 장씩, 작은 것 위에 큰 것을 올리지 않고 옮깁니다.

지금 쌓여 있는 호출(바깥부터):

옮기는 횟수 $T(n)$ 은 점화식⁠(recurrence relation)⁠ $T(n) = 2T(n-1) + 1$ 을 따릅니다. 1, 3, 7, 15, …, 곧 $2^n - 1$ 입니다. 이보다 적게는 할 수 없다는 것도 귀납법으로 보일 수 있습니다. 가장 큰 원판은 적어도 한 번 움직여야 하고, 처음 움직이는 순간에는 나머지 n−1장이 모두 세 번째 기둥에 모여 있어야 합니다. 거기까지 적어도 $T(n-1)$ 번, 마지막으로 움직인 뒤 그 위로 n−1장을 다시 모으는 데 또 적어도 $T(n-1)$ 번이 드니, 모두 $2T(n-1) + 1$ 번 이상입니다. 전설 속의 64장이라면 $2^{64} - 1 \approx 1.8 \times 10^{19}$ 번, 1초에 한 번씩 옮겨도 약 5800억 년이 걸립니다. 지수함수⁠(exponential function)⁠적인 증가의 전형입니다.

컴퓨터는 재귀 호출을 할 때마다 '어디까지 했는지'를 호출 스택⁠(call stack)⁠에 쌓아 두었다가, 작은 문제가 끝나면 꺼내서 이어 갑니다. 위의 ›로 이은 줄이 바로 그 스택입니다. 기저 사례를 빠뜨리거나 규칙이 문제를 기저 사례 쪽으로 줄이지 못하면 호출이 끝없이 쌓입니다. 실제 컴퓨터에서는 스택⁠(stack)⁠이 넘쳐 프로그램이 오류로 멈춥니다. 같은 작은 문제를 여러 번 부르는 재귀는 금세 느려집니다. 피보나치 수 $F_n = F_{n-1} + F_{n-2}$ 을 정의대로 재귀 호출하면 호출 수가 $F_n$ 에 비례해 불어나는데, 한 번 구한 답을 적어 두고 다시 쓰면 n번 남짓이면 됩니다. 이것이 동적 계획법⁠(dynamic programming)⁠입니다.

이어지는 곳. 유클리드 호제법⁠(Euclidean algorithm)⁠ $\gcd(a, b) = \gcd(b,\ a \bmod b)$ 은 자기를 한 번만 부르는 재귀이고, 문제를 반으로 나눠 두 번 부르는 것이 분할 정복⁠(divide and conquer)⁠입니다. 문장 안에 문장이 들어가는 언어의 구조는 문맥 자유 문법⁠(context-free grammar)⁠의 재귀 규칙으로 적고, 람다 계산⁠(lambda calculus)⁠에서는 함수⁠(function)⁠에 이름을 붙여 자기 자신을 부를 수 없는데도 재귀를 만들 수 있습니다. 고정점 결합자⁠(fixed-point combinator)⁠라는 장치가 함수 f를 받아 $Y f = f(Y f)$ 를 만족하는 값, 곧 f의 고정점⁠(fixed point)⁠을 만들어 주고, 이것이 f에게 '자기 자신'을 넘겨주는 구실을 하기 때문입니다. 칸토어 집합⁠(Cantor set)⁠은 '가운데 1/3을 지우고, 남은 두 조각에 같은 일을 한다'는 재귀로 정의되는 프랙털입니다. 망델브로 집합⁠(Mandelbrot set)⁠은 재귀라기보다 같은 식 $z \mapsto z^2 + c$ 를 되풀이하는 반복으로 그리지만, 경계 곳곳에 전체를 닮은 작은 복사본이 나타납니다. 재귀 호출이 뻗어 나간 모양은 트리⁠(tree)⁠가 됩니다. 타입⁠(type)⁠을 붙인 단순 타입 람다 계산⁠(simply typed lambda calculus)⁠에서는 고정점 결합자에 타입을 붙일 수 없어서 이런 재귀가 사라지고, 그 대신 모든 계산이 반드시 끝납니다. 자료도 재귀로 정의할 수 있어서, 리스트는 '빈 리스트이거나, 원소⁠(element)⁠ 하나와 더 짧은 리스트의 쌍'이고, 이런 정의를 타입으로 적은 것이 대수적 자료형⁠(algebraic data type)⁠입니다. 리스트 위의 함수를 '빈 리스트일 때의 값'과 '원소 하나와 나머지의 답을 합치는 방법' 두 가지로 정하는 재귀를 fold라 합니다. 이 두 가지를 주면 그런 함수가 꼭 하나 있다는 성질이 리스트 타입을 시작 대수로 만듭니다. '있다'는 쪽은 재귀로 함수를 정의할 수 있다는 뜻이고, '하나뿐'이라는 쪽은 수학적 귀납법으로 증명됩니다. 한편 f(n) = f(n + 1)처럼 해가 여럿인 재귀 정의(상수함수는 모두 해입니다)에서 프로그램이 실제로 계산하는 것은 그 가운데 '가장 적게 아는' 최소 고정점⁠(least fixed point)⁠, 여기서는 어떤 n에서도 끝나지 않는 함수라는 것이 영역 이론⁠(domain theory)⁠의 답입니다.

이 개념이 나오는 큰 생각무한을 다루는 법 자기 참조와 대각선

이 개념이 나오는 긴 글

조합론 세지 않고 세기 시의 운율을 세던 인도의 운율학자부터 오일러의 생성함수까지. 하나하나 늘어놓지 않고 경우의 수를 세는 법은 어떻게 자라났을까? 램지 이론 완전한 무질서는 없다 여섯 명이 모이면 서로 아는 세 사람이나 서로 모르는 세 사람이 반드시 있다. 충분히 크면 어디에나 질서가 숨어 있다는 이론과, 그것을 동전 던지기로 증명한 에르되시. 알고리즘과 복잡도 줄 세우기의 한계 카드 천 장을 가장 빨리 줄 세우는 방법은? 인구조사의 천공 카드에서 퀵정렬까지, 그리고 어떤 방법도 넘을 수 없는 n log n의 벽. 정보 이론과 압축 짧게 보내기 모스 부호는 왜 E를 점 하나로 보낼까? 섀넌의 엔트로피가 정한 압축의 한계와, 허프만 부호에서 JPEG까지 그 한계에 다가간 방법들. 타입 이론과 범주론 증명은 프로그램이다 러셀의 역설을 막으려던 '타입'이 프로그램의 실수를 막는 장치가 되었다. 명제를 타입으로, 증명을 프로그램으로 읽으면 둘이 규칙 하나하나까지 맞아떨어진다. 오늘날 수학자들은 그 사실로 컴퓨터에게 증명을 검사받는다. 게임과 증명 이기는 쪽이 존재한다 "이 판은 백이 이겼다"는 흑이 어떻게 두든 백에게 답이 있다는 말이다. 체스의 체르멜로 정리, ε–δ, 님의 이진법, 폰 노이만의 최소최대와 쌍대성, 논리의 한계를 재는 게임, 끝나지 않는 게임과 선택공리, 대화로 읽는 증명, 겨루며 배우는 신경망까지. 수학의 참을 두 사람의 게임으로 읽는다.

이 개념 위에 세워진 것

분할 정복 동적 계획법 게임 트리 탐색: 미니맥스와 몬테카를로 트리 탐색 영역 이론: 스콧과 재귀의 의미 F-대수와 fold: 재귀와 귀납의 범주론

이 개념을 언급하는 페이지

최대공약수와 유클리드 호제법
… \gcd(34, 21) = \gcd(21, 13) 입니다. 문제를 같은 모양의 더 작은 문제로 줄이는재귀의 전형입니다. 흔히 최대공약수를 구하려면 소인수분해가 필요하다고 생각합니다. 학교에서 12 = 2² …
피보나치 수열
… 알고 있었습니다. 피보나치 수는 파스칼의 삼각형의 얕은 대각선을 더해도 나옵니다. 정의를 그대로 옮긴재귀프로그램은 같은 값을 거듭 다시 계산합니다. F_n 을 구하는 호출 수는 F_n 자신과 같은 속도, 곧 …
람다 계산
… 순서는 정규형이 있으면 반드시 찾아낸다는 것이 알려져 있습니다(표준화 정리). 이름 없는 함수로는 되부름(재귀)을 어떻게 할까요? 함수 g에 넣었을 때 그대로 돌아오는 값, 곧 g\,z = z 인 z를 g의 …
처치–튜링 논제
… 클리니⟧가 다듬은 재귀 함수가 있었습니다. 재귀 함수는 0과 '다음 수'에서 출발해 함수 합성, 되부름(재귀), '조건을 만족하는 가장 작은 수 찾기'만으로 만들어지는 자연수 함수입니다. 여기에 튜링의 ⟦튜링 …
문맥 자유 문법
… 촘스키와 쉬첸베르제). aⁿbⁿ을 만드는 규칙 S → aSb는 자기 자신을 다시 품습니다. 이 되풀이(재귀) 덕분에 문맥 자유 문법은 '열린 것은 반드시 닫힌다'는 중첩을 얼마든지 깊이 적을 수 있고, 바로 이 …
수학적 귀납법
… 항 하나가 앞의 여러 항으로 정해지는 점화식의 성질도 대개 이렇게 증명합니다. 프로그램과 귀납법.재귀는 귀납법을 거꾸로 돌린 것입니다. 프로그램이 가장 작은 경우를 옳게 풀고, 큰 경우의 답을 더 작은 …
점화식
… 피보나치 수열 a_n = F_{n+1} 이 됩니다. 작은 경우의 답으로 큰 경우의 답을 짓는 이 생각이재귀와 동적 계획법의 뿌리입니다. 아래는 a_n = p\,a_{n-1} + q\,a_{n-2} + c 꼴의 …
카탈랑 수
… 트리의 모양도 같은 이유로 C_n 가지입니다. 뿌리의 왼쪽 가지와 오른쪽 가지가 A와 B입니다(트리,재귀). 행렬 n+1개를 곱하는 순서(괄호 치는 방법)도 C_n 가지입니다. 이 수는 금세 너무 커지므로, …
알고리즘
… 곳. 알고리즘을 설계하는 대표적인 틀이 몇 가지 있습니다. 문제를 같은 모양의 더 작은 문제로 줄이는재귀, 반으로 나눠 각각 풀고 합치는 분할 정복, 겹쳐 나오는 작은 문제의 답을 표에 적어 두고 다시 쓰는 …
분할 정복
분할 정복은재귀의 한 형태입니다. 크기 n인 문제를 크기 n/2인 문제 몇 개로 나누고(분할), 각각을 같은 방법으로 푼 …
정렬 알고리즘
… 퀵정렬 은 기준 원소(피벗)를 하나 골라 그보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 가른 뒤 양쪽을재귀로 정렬합니다. 여기서는 구간의 마지막 원소를 피벗으로 씁니다. 무작위로 섞인 입력에서는 평균 비교 횟수가 …
동적 계획법
재귀로 문제를 작은 문제로 쪼개다 보면 같은 작은 문제가 여러 번 다시 나오는 일이 많습니다. 피보나치 수 …
트리
… 폴더 구조처럼 위아래가 생깁니다. 뿌리 있는 트리는 '뿌리 하나와 그 아래 매달린 더 작은 트리들'이라는재귀적인 정의를 가지고, 그래서 트리 위의 계산은 대개 재귀로 짭니다. 자식이 많아야 둘이고 왼쪽 자식과 …
콜모고로프 복잡도
… 최적 답을 표에 채워 가는 동적 계획법으로 정확히 찾을 수 있고, 답은 되풀이 안에 되풀이가 든재귀적인 모양입니다. 문자열: . 비트를 눌러 뒤집어 보세요. 파란 칸이 1, 어두운 칸이 0입니다. 아래 …
게임 트리 탐색: 미니맥스와 몬테카를로 트리 탐색
… 다할 때의 결과이고, 그 값을 준 자식이 둘 수입니다. 이것이 미니맥스이며, 트리를 내려갔다 올라오는재귀로 짧게 적힙니다. v(n) = \max_{c}\, v(c)\ \ (n\text{: MAX}), …
대수적 자료형
… 구멍을 뚫는다는 것은 미분과 테일러 급수의 셈을 자료 구조에서 다시 보는 일입니다. 되부르는 타입은재귀로 처리하고, 그 되부름이 반드시 끝난다는 보장은 수학적 귀납법과 같은 원리에서 나옵니다. 타입 변수를 …
타입 추론: 힌들리–밀너
… 문법⟧으로 파싱해 얻고, 단일화는 두 나무를 겹쳐 맞추는 알고리즘이라, 발생 검사를 빼먹으면 나무에되부름하는 고리가 생겨 버립니다. 하위 타입이 끼어들면 같음의 방정식 대신 부등식 X\le Y 를 풀어야 해서 …
의존 타입
… 되부름이다. 자연수를 0과 succ(다음 수)로 짓고(페아노의 방식), 덧셈을 첫째 인자에 대한되부름으로 정의합니다: 0 + m = m , \mathrm{succ}\,k + m = …
영역 이론: 스콧과 재귀의 의미
… 1, 아니면 n · fact(n − 1). 식의 양쪽에 fact가 있으니 이것은 정의라기보다 방정식입니다.재귀를 처음 배울 때는 '같은 모양의 더 작은 문제로 줄인다'고 이해하고 넘어가지만, 방정식이라면 물어야 할 …
F-대수와 fold: 재귀와 귀납의 범주론
… 모든 n이 P를 거쳐 가니 P = ℕ입니다. 곧 수학적 귀납법은 시작 대수의 '하나뿐'이 하는 말 이고,재귀로 정의하는 것은 시작 대수의 '있다'가 하는 말입니다. 목록에 대해서도 같은 논증으로 '빈 목록에서 …

이 페이지가 가리키는 개념

점화식 지수함수 eˣ 피보나치 수열 동적 계획법 최대공약수와 유클리드 호제법 분할 정복 문맥 자유 문법 람다 계산 고정점 칸토어 집합 망델브로 집합 트리 단순 타입 람다 계산 대수적 자료형 F-대수와 fold: 재귀와 귀납의 범주론 영역 이론: 스콧과 재귀의 의미