recursion.md

재귀함수

재귀함수recursive function는 함수 안에서 자기 자신을 다시 호출하는 함수이다. 큰 문제를 같은 모양의 더 작은 문제로 나누고, 작은 문제의 답으로 큰 문제의 답을 만든다.

4! 은 4 × 3 × 2 × 1 이다. 이 식은 4 × 3! 으로 쓸 수 있고, 3! 은 다시 3 × 2! 으로 쓸 수 있다. n! 을 구하는 문제가 (n - 1)! 을 구하는 문제로 작아진다.

n!=n×(n−1)!n! = n \times (n - 1)!

기저 사례와 재귀 단계

재귀함수는 두 부분으로 이루어진다.

기저 사례가 없으면 호출이 끝나지 않는다. 함수를 호출할 때마다 매개변수와 지역 변수를 담는 공간이 스택stack 메모리에 쌓이므로, 호출이 끝없이 이어지면 스택 메모리가 바닥나 프로그램이 비정상 종료된다. 이를 스택 오버플로우stack overflow라 한다.

재귀 단계는 입력을 반드시 기저 사례 쪽으로 줄여야 한다. factorial(n) 이 factorial(n + 1) 을 호출하면 기저 사례가 있어도 도달하지 못한다.


팩토리얼

#include <iostream>

using namespace std;

long long factorial(int n)
{
    if (n <= 1) // base case
    {
        return 1;
    }
    return n * factorial(n - 1);
}

int main()
{
    cout << factorial(4) << '\n';
    return 0;
}
24
image

위 그림은 factorial(4) 의 호출 과정이다. 왼쪽 위에서 아래로 내려가며 호출하고, 기저 사례인 파란 factorial(1) 에서 처음으로 값을 반환한다. 이후 아래에서 위로 올라오며 반환값이 정해진다. factorial(2) 는 2 × 1 = 2, factorial(3) 은 3 × 2 = 6, factorial(4) 는 4 × 6 = 24 를 반환한다.

factorial(4) 는 factorial(3) 이 반환할 때까지 끝나지 않는다. 따라서 factorial(1) 이 호출된 순간에는 네 함수가 모두 스택에 쌓여 있다.


반환형은 long long 이다. 13! 은 6,227,020,800 으로 int 의 최댓값 2,147,483,647 을 넘는다. long long 은 20! 까지 담을 수 있다.

기저 사례를 n <= 1 로 두어 factorial(0) 도 1 을 반환한다. 0! 은 1 로 정의된다. 음수의 팩토리얼은 정의되지 않지만, 음수를 넣어도 바로 1 을 반환하므로 호출이 끝없이 이어지지 않는다.


같은 계산을 반복문으로 쓰면 아래와 같다.

long long factorial(int n)
{
    long long ret = 1;
    for (int i = 2; i <= n; i++)
    {
        ret *= i;
    }
    return ret;
}

피보나치 수

피보나치 수는 앞의 두 수를 더해 다음 수를 만든다. 0, 1, 1, 2, 3, 5, 8, 13, ... 이다.

F(0)=0,F(1)=1F(n)=F(n−1)+F(n−2)\begin{gathered} F(0) = 0, \quad F(1) = 1 \\ F(n) = F(n - 1) + F(n - 2) \end{gathered}

식 그대로 재귀함수가 된다. 기저 사례는 F(0) 과 F(1) 두 개가 된다.

#include <iostream>

using namespace std;

int fibonacci(int n)
{
    if (n <= 1) // base case : F(0) = 0, F(1) = 1
    {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main()
{
    for (int i = 0; i <= 10; i++)
    {
        cout << fibonacci(i) << " ";
    }
    cout << '\n';
    return 0;
}
0 1 1 2 3 5 8 13 21 34 55
image

위 그림은 fibonacci(5) 의 호출 과정이다. 한 번의 호출이 두 번의 호출로 갈라지고, f(1) 과 f(0) 에서 멈춘다. 파란 f(2) 는 세 번 호출되는데, 매번 같은 값 1 을 처음부터 다시 계산한다. f(3) 도 두 번 호출된다. 이처럼 같은 작은 문제가 여러 번 나타나는 것을 중복 부분 문제overlapping subproblems라 한다.

fibonacci(5) 는 함수를 15 번 호출한다. n 이 1 커질 때마다 호출 횟수가 약 1.6 배씩 늘어나서, fibonacci(30) 은 2,692,537 번 호출한다.


메모이제이션

한 번 구한 값을 배열에 저장해 두고, 같은 입력이 다시 들어오면 계산하지 않고 저장한 값을 반환한다. 이를 메모이제이션memoization이라 한다.

#include <iostream>
#include <vector>

using namespace std;

vector<long long> memo(91, -1);

long long fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    if (memo[n] != -1) // already computed
    {
        return memo[n];
    }
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main()
{
    cout << fibonacci(90) << '\n';
    return 0;
}
2880067194370816120

memo[n] 이 -1 이면 아직 구하지 않은 값이다. 각 n 을 한 번씩만 계산하므로 fibonacci(90) 도 바로 끝난다. 그림에서 f(4) 아래의 두 번째 f(2) 와 오른쪽 f(3) 은 아래로 갈라지지 않고 저장한 값을 바로 반환하며, 오른쪽 f(3) 아래의 호출은 일어나지 않는다. 작은 문제의 답을 저장해 두고 큰 문제를 푸는 방법을 동적 계획법dynamic programming이라 한다.


최대공약수

두 수 a, b 의 최대공약수는 b 와 a % b 의 최대공약수와 같다. 이를 유클리드 호제법이라 한다. b 가 0 이면 a 가 최대공약수이다.

gcd⁡(a,b)=gcd⁡(b,a mod b),gcd⁡(a,0)=a\gcd(a, b) = \gcd(b, a \bmod b), \quad \gcd(a, 0) = a

gcd(48, 18) 은 아래와 같이 진행한다.

gcd(48, 18)  →  48 % 18 = 12
gcd(18, 12)  →  18 % 12 = 6
gcd(12, 6)   →  12 % 6  = 0
gcd(6, 0)    →  6
#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    if (b == 0) // base case
    {
        return a;
    }
    return gcd(b, a % b);
}

int main()
{
    cout << gcd(48, 18) << '\n';
    return 0;
}
6

a % b 는 b 보다 작으므로 두 번째 인자는 호출마다 줄어들고, 결국 0 이 되어 기저 사례에 도달한다.


거듭제곱

a 의 n 제곱은 a 를 n 번 곱한다. n 이 짝수이면 ana^n 을 an/2a^{n/2} 의 제곱으로 나눌 수 있다.

an={1(n=0)(an/2)2(n is even)(a(n−1)/2)2×a(n is odd)a^n = \begin{cases} 1 & (n = 0) \\ (a^{n/2})^2 & (n \text{ is even}) \\ (a^{(n-1)/2})^2 \times a & (n \text{ is odd}) \end{cases}

2102^{10} 은 아래와 같이 구한다.

210=(25)225=(22)2×222=(21)221=(20)2×220=1\begin{aligned} 2^{10} &= (2^5)^2 \\ 2^5 &= (2^2)^2 \times 2 \\ 2^2 &= (2^1)^2 \\ 2^1 &= (2^0)^2 \times 2 \\ 2^0 &= 1 \end{aligned}
#include <iostream>

using namespace std;

long long power(long long a, int n)
{
    if (n == 0) // base case
    {
        return 1;
    }
    long long half = power(a, n / 2);
    if (n % 2 == 0)
    {
        return half * half;
    }
    return half * half * a;
}

int main()
{
    cout << power(2, 10) << '\n';
    return 0;
}
1024

n 이 호출마다 절반이 되므로 호출 횟수는 약 log⁡2n\log_2 n 번이다. a 를 하나씩 곱하는 반복문은 n 번 곱한다. n 이 1,000,000 이면 반복문은 1,000,000 번 곱하고, 재귀함수는 21 번 호출한다.

power(a, n / 2) 를 half 에 한 번만 받아 두는 것이 중요하다. power(a, n / 2) * power(a, n / 2) 로 쓰면 같은 호출을 두 번 하게 되어, n 이 1,000,000 일 때 반복문의 곱셈 횟수보다 많은 2,097,151 번을 호출한다.


하노이 탑

기둥 A, B, C 가 있고, A 에 크기가 다른 원판 n 개가 큰 것부터 쌓여 있다. 원판을 모두 C 로 옮기는데, 한 번에 맨 위 원판 하나만 옮기고, 큰 원판을 작은 원판 위에 놓을 수 없다.

가장 큰 원판을 C 로 옮기려면 그 위의 n - 1 개가 모두 비켜 있어야 한다. 따라서 n 개를 옮기는 문제는 세 단계로 나뉜다.

  1. 위의 n - 1 개를 A 에서 B 로 옮긴다.
  2. 가장 큰 원판을 A 에서 C 로 옮긴다.
  3. B 의 n - 1 개를 C 로 옮긴다.
image

위 그림은 원판이 3 개일 때 세 단계를 거친 모습이다. 파란 원판이 가장 큰 원판이다. 1단계와 3단계의 회색 원판 2 개를 옮기는 일은 원판 2 개짜리 하노이 탑 문제이므로 같은 함수를 다시 호출한다. 이때 출발, 도착, 거쳐 가는 기둥이 바뀐다.

#include <iostream>

using namespace std;

void hanoi(int n, char from, char via, char to)
{
    if (n == 0) // base case
    {
        return;
    }
    hanoi(n - 1, from, to, via);
    cout << n << " : " << from << " -> " << to << '\n';
    hanoi(n - 1, via, from, to);
}

int main()
{
    hanoi(3, 'A', 'B', 'C');
    return 0;
}
1 : A -> C
2 : A -> B
1 : C -> B
3 : A -> C
1 : B -> A
2 : B -> C
1 : A -> C

출력의 앞 숫자는 옮긴 원판의 크기이다. 위의 세 줄이 1단계, 가운데 3 : A -> C 가 2단계, 아래 세 줄이 3단계이다.

원판 n 개를 옮기는 횟수는 n - 1 개를 두 번 옮기고 한 번 더 옮기므로 2n−12^n - 1 번이다. 원판이 3 개이면 7 번이다.


재귀함수와 반복문

재귀함수는 호출할 때마다 스택에 공간을 쌓으므로, 같은 계산을 하는 반복문보다 메모리를 더 쓰고 호출하는 비용이 든다. 호출이 깊어지면 스택 오버플로우가 일어난다. 팩토리얼처럼 반복문으로 바로 쓸 수 있는 계산은 반복문으로 쓰는 것이 낫다.

하노이 탑처럼 문제가 같은 모양의 작은 문제 여러 개로 나뉘는 경우에는 재귀함수가 식을 그대로 옮긴 코드가 된다. 트리 탐색, 순열과 조합 생성, 분할 정복도 같은 경우이다.