(C#) 15. 코드의 흐름 제어 (factorial)

자기 자신을 부르는 함수

팩토리얼은 정의 자체가 자기 참조다.

5! = 5 * 4!
n! = n * (n-1)!

이걸 코드로 두 가지로 쓸 수 있다. 반복문으로 풀어 쓰거나, 정의를 그대로 옮기거나.

using System;

namespace ex3
{
    class Program
    {
        // 팩토리얼
        static int Factorial(int n)
        {
            int ret = 1;
            for (int num = 1; num <= n; num++)
            {
                ret *= num;
            }
            return ret;
        }

        static int Factorial1(int n)
        {
            if (n <= 1)
                return 1;
            return n * Factorial1(n - 1);
        }
        static void Main(string[] args)
        {
            // 5! = 5 * 4!
            // 5! = 5 * 4 * 3 * 2 * 1
            // n! = n * (n-1) * ... * 1 (n >= 1)
            int ret = Factorial(5);
            int ret1 = Factorial1(5);

            Console.WriteLine(ret);
            Console.WriteLine(ret1);
        }
    }
}

둘 다 120을 찍는다.

재귀에는 멈출 조건이 반드시 있어야 한다

if (n <= 1)
    return 1;

이 두 줄이 없으면 Factorial1(5)가 4, 3, 2, 1, 0, -1, -2 ...로 끝없이 내려간다. 재귀에서 이걸 기저 조건이라고 부른다.

그리고 재귀 호출은 기저 조건에 가까워지는 방향이어야 한다. Factorial1(n - 1)이 그렇다. 실수로 Factorial1(n)이라고 쓰면 조건이 있어도 영원히 돈다.

n <= 1로 쓴 게 n == 1보다 나은 선택이었다. 0!은 정의상 1이고, n == 1이었다면 0에서 안 걸려서 음수로 내려간다.

13! 부터 값이 이상해진다

Factorial(13)을 넣어봤다.

1932053504

13!은 6,227,020,800이다. 전혀 다른 값이 나왔다.

int의 최대값이 2,147,483,647이라 넘친 것이다. 1편에서 본 그대로, C#은 기본적으로 오버플로를 조용히 넘긴다. 계산은 계속되고 값만 틀린다.

n	n!	결과
12	479,001,600	int 안에 들어간다
13	6,227,020,800	넘친다

long으로 바꾸면 20!까지 된다. 21!은 또 넘친다. 팩토리얼은 워낙 빠르게 커져서 타입을 키워도 몇 개 더 갈 뿐이다.

static long Factorial(int n)
{
    long ret = 1;
    for (int num = 1; num <= n; num++)
        ret *= num;
    return ret;
}

계산 결과를 믿을 수 있게 하려면 checked로 감싸서 넘치는 순간 예외를 받는 게 낫다.

checked
{
    ret *= num;      // 넘치면 OverflowException
}

정말 큰 값이 필요하면 System.Numerics.BigInteger가 있다. 자릿수 제한이 없는 대신 느리다.

음수를 넣으면 1이 나온다

Factorial(-5)를 넣으면 두 버전 다 1을 돌려준다.

반복문 쪽은 for (num = 1; num <= -5; ...)가 한 번도 안 돌아서 초기값 1이 그대로 나온다. 재귀 쪽은 n <= 1에 바로 걸린다.

음수 팩토리얼은 정의되지 않으니 1은 틀린 답이다. 9편에서 소수 판정에 1을 넣었을 때와 같은 종류의 문제다. 루프가 한 번도 안 도는 경우를 따로 안 챙긴 것이다.

static long Factorial(int n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
    long ret = 1;
    for (int num = 2; num <= n; num++) ret *= num;
    return ret;
}

조용히 틀린 값을 돌려주는 것보다 예외를 던지는 편이 낫다. 잘못된 값이 계속 흘러가면 한참 뒤에 엉뚱한 곳에서 증상이 나온다.

num을 2부터 시작한 건 1을 곱하는 게 무의미해서다. 결과는 같다.

재귀가 깊어지면 프로세스가 죽는다

Factorial1(100000)을 넣어봤다.

Process is terminated due to StackOverflowException.

함수를 부를 때마다 스택에 호출 정보가 쌓인다. 재귀가 깊어지면 스택 공간이 바닥난다. .NET의 기본 스택은 스레드당 1 MB 정도라 수만 단계쯤에서 넘친다.

여기서 중요한 게 있다. StackOverflowException은 try/catch로 잡을 수 없다. .NET 2.0부터 이 예외는 프로세스를 즉시 종료시킨다. 스택이 없는 상태에서 예외 처리 코드를 실행할 수 없기 때문이다.

try { Factorial1(100000); }
catch (Exception) { Console.WriteLine("잡았다"); }   // 실행되지 않는다

다른 예외와 성격이 다르다는 걸 이때 알았다. 예외 처리로 방어할 수 없으니 깊이가 커질 수 있는 재귀는 애초에 반복문으로 짜야 한다.

일부 언어는 꼬리 재귀를 반복문으로 바꿔주지만, C#은 그걸 보장하지 않는다. Factorial1은 n * Factorial1(...)이라 곱셈이 남아 있어서 꼬리 재귀도 아니다.

그래서 둘 중 무엇을 쓰나

팩토리얼처럼 단순한 경우에는 반복문이 낫다. 스택을 안 쓰고, 호출 비용도 없고, 깊이 제한도 없다.

재귀가 나은 건 문제 구조가 원래 재귀적일 때다. 트리 순회나 미로 탐색이 그렇다. 반복문으로 짜려면 스택 자료구조를 직접 만들어야 해서 오히려 코드가 길고 읽기 어려워진다.

이 시리즈에서도 40편 이후 미로와 트리를 다루면서 재귀가 다시 나온다. 그때는 재귀가 맞는 선택이다.

정리하면

• 재귀에는 기저 조건과, 그 조건에 가까워지는 호출이 둘 다 있어야 한다
• n <= 1로 쓰면 0!도 처리된다
• 팩토리얼은 13!에서 int를, 21!에서 long을 넘긴다. 오버플로는 조용히 지나간다
• 음수 입력에서 루프가 한 번도 안 돌아 1이 나온다. 잘못된 입력은 예외로 막는다
• StackOverflowException은 catch할 수 없고 프로세스가 그대로 죽는다
• 깊이가 커질 수 있으면 반복문, 문제 구조가 재귀적이면 재귀