재귀 (Recursion) 알고리즘

재귀(Recursion) 알고리즘은 재귀 함수를 이용하는 상당히 광범위한 프로그래밍 기법인데요. 여기서 재귀 함수란 함수 내부에서 자기 자신을 다시 호출하는 특수한 형태의 함수를 의미합니다.

재귀 알고리즘

재귀 알고리즘을 사용하면, 크고 복잡한 문제가 주어졌을 때, 문제의 크기를 결과를 얻을 수 있을 정도까지 점진적으로 줄인 다음에, 바로 그 결과를 이용하여 거꾸로 점점 더 큰 문제를 풀다가, 결국에는 맨 처음에 주어진 크기의 문제를 해결할 수 있습니다.

예를 들어, 수학 시간에 배웠던 계승(Factorial)을 구하는 로직을 재귀 알고리즘으로 구현해보겠습니다.

def factorial(n):
    if n == 0: # 기저 조건
        return 1
    return n * factorial(n-1) # 재귀 호출

재귀 함수는 대부분 위와 같이 비슷한 형태를 띠게 되는데요. 맨 위에서 기저 조건을 설정하고, 그 아래에서는 자기 자신을 호출합니다.

기저 조건에 도달하기 위해서 매번 호출할 때 마다 더 작거나 큰 인수를 넘기며, 자기 자신을 몇 번 호출해야 할지는 해결해야 할 문제에 따라 다르겠습니다.

factorial() 함수에 인자로 5를 넘기면 재귀 호출이 어떻게 일어날지를 시각화해보았는데요.

factorial(5)
    factorial(4)
        factorial(3)
            factorial(2)
                factorial(1)
                    factorial(0)
                    ↳ 1
                ↳ 1 * 1 = 1
            ↳ 2 * 1 = 2
        ↳ 3 * 2 = 6
    ↳ 4 * 6 = 24
↳ 5 * 24 = 120

호출 스택이 깊어짐에 따라 인수가 점점 작아지고 결국 기저 조건에 도달하면, 다시 스택을 타고 거꾸로 거슬러 올라오면서 결과가 계산이 되는 것을 볼 수 있습니다. 즉, 재귀 알고리즘은 위에서 아래로, 즉 Top-down 방향으로 문제에 접근하게 되며, 더 큰 문제의 결과를 구하려면 더 작은 문제의 결과가 구해질 때까지 기다리는 과정을 수반합니다.

재귀 알고리즘으로 풀 수 있는 또 다른 유명한 문제인 피보나치(Fibonacci) 수열에 대해서는 관련 글을 참고 바랍니다.

코딩 테스트에서 활용

코딩 테스트를 보면 적어도 두 문제 중 한 문제는 재귀 알고리즘으로 풀 수 있을 정도로, 재귀 알고리즘을 통해 해결할 수 있는 문제가 코딩 테스트에서는 참 많이 출제됩니다.

특히, 링크드 리스트, 이진 트리, 그래프와 같은 자료 구조와 관련된 문제에서 재귀 알고리즘이 빛을 발휘하는데요. 이러한 자료 구조는 Top-down 방향으로 탐색해야하는 경우가 많기 때문입니다.

뿐만 아니라, 순열(Permutation)이나 조합(Combination)과 같이 경우의 수를 따지는 문제에서도 재귀 알고리즘이 많이 활용되는데요. 주어진 큰 문제를 해결하기 위해서는, 재귀 함수를 통해서 작은 문제로 쪼개서 해결한 후에, 그 결과를 합쳐야 하기 때문입니다.

대부분의 인간은 순차적으로 사고하는 데 더 익숙하기 때문에 재귀 알고리즘을 처음 접하시면 아주 어렵게 느껴질 수 있습니다. 따라서, 코딩 테스트를 준비하시는 분들은 재귀 알고리즘을 사용하는 문제를 많이 푸셔서 재귀적으로 사고하는 능력을 키우는 것이 중요하겠습니다.

주의 사항

반복 알고리즘을 사용하는 코드를 작성할 때 각별히 조심해야하는 부분이 몇 가지 있는데요.

우선 자기 자신을 호출하는 재귀 함수의 특성 상 무한 루프에 빠지기기 아주 쉽습니다. 그래서, 재귀 함수가 반드시 종료될 수 있도록 항상 기저 조건(base case)을 신중하게 설정해야합니다.

두 번째로 주의할 부분은 그 유명한 스택 오버플로우(Stack Overflow) 문제인데요. 모든 코드는 결국 물리적인 하드웨어에서 돌아가기 때문에 호출 스택의 크기가 제한이 되어 있습니다. 그래서 재귀 알고리즘이 수행되는 도중, 호출 스택이 너무 깊어져서 이 제한된 크기를 초과하게 되면, 프로그램이 강제 종료될 수 잇습니다.

참고로, 이러한 재귀 알고리즘의 위험성 때문에 코딩 테스트에서는 자주 볼 수 있는 재귀 알고리즘을 상용 소프트웨어를 개발할 때는 기피하는 경향이 있는데요. 무한 루프에 빠지든 스택 오버플로우가 발생하든 해당 소프트웨어는 작동할 수 없는 상태가 되기 때문입니다. 게다가 재귀 알고리즘으로 작성된 코드는 사람이 이해하기가 비교적 어렵고 유지보수도 어려운 편에 속하기 때문에, 여러 개발자가 협업하는 프로젝트에는 재귀 알고리즘을 납용하거나 오용하시면 곤란하겠습니다.

반복 알고리즘과 비교

재귀 알고리즘에게는 숙명의 라이벌인 반복(Iteration) 알고리즘이 있는데요. 동일한 문제를 반복 알고리즘으로도 풀 수 있고 재귀 알고리즘으로도 풀 수 있는 경우가 많아서 이 둘을 자주 비교하게 됩니다.

예를 들어, 맨 처음에 재귀 알고리즘으로 작성한 계승을 구하는 코드를 반복 알고리즘으로 어렵지 않게 재작성할 수 있습니다.

def factorial(n):
    result = 1
    for i in range(n):
        result *= i + 1
    return result

코딩 면접에서는 지원자가 재귀 알고리즘으로 답안을 작성했다면, 동일한 로직을 반복 알고리즘으로도 작성해보라고 하거나, 또는 반대로 반복 알고리즘으로 짠 코드를 재귀 알고리즘으로 구현해보라고 요구하는 경우가 있습니다. 그러므로, 재귀 알고리즘의 코드를 반복 알고리즘으로, 그리고 반대로 반복 알고리즘의 코드를 재귀 알고리즘으로 짜는 연습을 하시면 큰 도움이 될 것 입니다.

복잡도 분석

재귀 알고리즘의 복잡도 분석을 어려워하시는 분들이 많은데요. 반복 알고리즘은 단순히 코드를 읽어서 반복문의 구조만 파악하면 되지만, 재귀 알고리즘은 재귀 함수가 어떻게 호출될지를 머리 속으로 그려봐야 하기 때문입니다. 즉, 전체 함수 호출 트리를 그릴 수 있어야 합니다.

각 단계에서 몇 번의 재귀 호출이 연쇄적으로 일어나는지를 알면 시간 복잡도를 계산할 수 있고, 호출 스택의 최대 깊이를 통해서 공간 복잡도를 구할 수 있습니다.

예를 들어서, 함수 내에서 재귀 호출이 한 번만 일어나는 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(n)이 됩니다. 총 n 번이 함수 호출이 일어나고, 호출 스택이 깊이도 n이기 때문입니다.

f(0)
    f(1)
        f(2)
            f(3)
                f(4)

함수 내에서 재귀 호출이 한 번 더 일어나면 호출 스택이 한 단계 깊어질 때 마다 호출 수가 2배씩 늘어나기 때문에 시간 복잡도가 O(2^n)이 되며, 그래도 호출 스택이 깊이는 변하지 않기 때문에 공간 복잡도는 O(n)이 됩니다.

여기서 재귀 호출이 한 번 더 일어나게 되면 각 단계에서 호출 수가 3배씩 늘어나기 때문에 시간 복잡도가 O(3^n)이 되고, 공간 복잡도는 여전히 O(n)이 됩니다.

이 것은 해당 재귀 함수 내에서 재귀 호출을 하는 부분을 제외하고는 O(1), 즉 상수 시간이 걸린다는 가정한 복잡도 분석이고요. 만약에 함수 내에서 반복문이 있거나 추가적인 자료구조를 사용한다면 시간 복잡도와 공간 복잡도는 그에 따라 비약적으로 더 늘어날 것입니다.

재귀 알고리즘에서 불필요한 중복 계산을 제거해주는 성능 최적화 기법인 메모이제이션(Memoization)에 대해서는 별도 글에서 다루고 있습니다.