재귀 함수로 프로그래밍 사고 전환하기

Feb 29, 2024

Published byJynn

999

Recursive Functions with Java

프로그래밍 학습은 때때로 새로운 사고 패러다임을 받아들이며 어려운 개념을 이해하게 되는 관문입니다. 이러한 전환 중 하나는 재귀적 사고입니다. 재귀 함수는 우리에게 루프와 반복을 넘어서 더 깊은 차원의 문제 해결 기법을 제공합니다.

재귀(Recursion)는 사전적으로 다시 돌아가다, 되풀이되다라는 뜻으로, 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 것을 말합니다.

프로그래밍에서 재귀 함수(Recursive Function)란 함수 내에서 자기 자신을 다시 호출하는 행위, 혹은 구조적인 모습을 의미합니다. 즉, 함수가 자기 자신을 참조하는 것입니다. 이것은 반복문을 사용하는 것과 같은 목적을 달성하며, 특정 조건이 충족되면 종료됩니다.

Structure of Recursive Functions

재귀 함수는 크게 두 가지 주요 구성 요소로 나눌 수 있습니다:

기저 조건(Base Case):
- 기저 조건 (또는 종료 조건)은 재귀 함수가 종료해야 할 조건을 정의합니다. 이는 재귀의 무한 반복을 방지하는 역할을 합니다.
- 모든 재귀 함수는 반드시 하나 이상의 기저 조건을 가지고 있어야 합니다. 기저 조건은 일반적으로 문제의 가장 간단하고 명백한 해답을 제공하는 경우입니다.
- 기저 조건을 만족하면, 함수는 새로운 재귀 호출을 중단하고 호출 스택에서 빠져나옵니다.
- 기저 조건이 없으면 재귀 함수는 무한히 자신을 호출함으로써 프로그램이 비정상적으로 종료될 수 있습니다.
재귀 호출(Recursive Case):
- 재귀 호출은 함수가 자신을 다시 호출하는 부분입니다. 이렇게 함으로써 문제를 더 작은 부분으로 분해하고 해결을 단순화하는 역할을 합니다.
- 이 부분에서 함수는 주어진 작업을 수행하고, 문제의 크기가 아직 충분히 줄어들지 않았다면 자신을 다시 호출합니다.
- 이렇게 함수가 자신을 반복적으로 호출함으로써, 자신의 작업을 여러 번 수행할 수 있습니다.

이렇게 제어를 담당하는 다중조건과 함수가 자기 자신을 참조하는 호출은 재귀 함수의 가장 중요한 특징입니다. 이 두 구성 요소가 잘 조화되어야 재귀 함수가 원활하게 작동하며, 작업을 성공적으로 완료할 수 있습니다.

Execution of Recursive Functions

재귀 함수의 작동방식을 이해하기 위해 팩토리얼 계산이라는 대표적인 예시를 살펴보겠습니다.

팩토리얼(Factorial)은 n! 이라는 기호로 표현되며, 이는 주어진 수 n부터 1까지의 모든 양의 정수를 연속적으로 곱하는 연산을 의미합니다. 즉, n! = n * (n-1) * (n-2) * ... * 2 * 1입니다. 가령, 5!는 5 * 4 * 3 * 2 * 1, 즉 120이 됩니다.

Java로 작성된 재귀 함수 형태의 팩토리얼 계산 코드는 다음과 같습니다:

public int factorial(int n) {
    if (n == 0) return 1; // ¹Base Case
    else return factorial(n - 1) * n; // ²Recursive Case
}

¹ 종료 조건 (Base Case):
- 파라미터 n이 0인 경우, 팩토리얼 함수는 종료됩니다.
- 팩토리얼 연산에서 0의 팩토리얼 값은 1로 정의됩니다.
- 따라서, n이 0일 때, 함수는 1을 반환하고 재귀 호출을 종료합니다. 이 조건이 없으면 함수는 무한히 자기 자신을 호출하게 되어 스택 오버플로우 오류를 발생시킵니다.
² 재귀 호출 (Recursive Case):
- 파라미터 n이 0이 아닌 경우, 팩토리얼 함수는 자기 자신을 호출합니다.
- 현재 n 값과 n - 1에 대한 팩토리얼의 곱을 반환합니다.
- 여기서 factorial(n - 1)은 자신을 다시 호출하는 재귀 호출입니다: n - 1로 n값을 서서히 줄이며 n이 0에 도달하면 재귀 호출을 멈춥니다. 이를 통해 팩토리얼 계산을 구현합니다.

재귀 함수는 함수 호출이 일어날 때마다 새로운 스택 프레임을 생성하여 이를 메모리 내 콜 스택에 쌓아 올립니다. 각 함수 호출은 독립적으로 자신의 계산을 수행하며 필요한 경우 상위 호출로부터 인자를 받아 서로 다른 스택 프레임 간에 정보를 공유합니다. 예를 들어 5!을 계산하는 과정을 단계별로 표현하면 다음과 같습니다:

    factorial(5)  # 결과: 120
        factorial(4)  # 결과: 24
            factorial(3)  # 결과: 6
                factorial(2)  # 결과: 2
                    factorial(1)  # 결과: 1
                        factorial(0)
                        return 1
                    return 1 * 1
                return 2 * 1
            return 3 * 2
        return 4 * 6
    return 5 * 24

Recursion vs. Iteration

재귀 함수와 반복문은 모두 동일한 작업을 반복해서 수행하는 데 사용되므로 처음 보기에는 매우 비슷하게 느껴질 수 있습니다. 그러나 이 두 가지는 작동 방식과 용도가 서로 다르며, 이는 각각의 적절한 사용 사례와 관련된 이점과 단점을 생성합니다.

반복문을 이용하면, 문제를 해결하기 위해 필요한 모든 단계를 순차적으로 따라가게 됩니다. 숫자 n의 팩토리얼을 계산하고자 할 때, 1부터 n까지의 수를 차례대로 곱하는 작업을 생각하게 됩니다. 이는 각 단계를 하나씩 파고드는 저차원적인 접근 방식이지만, 이 방법은 결과를 명확하게 도출하는 데 있어 직관적이고 효과적입니다.

동일한 팩토리얼 계산을 반복문으로 구현한 예시는 다음과 같습니다:

public int factorial(int n) {
    int result = 1;
    for(int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

반복문의 장점
- 반복은 일반적으로 재귀에 비해 메모리 효율이 더 좋습니다. 그 이유는 콜 스택에 함수 호출에 대한 정보를 저장할 필요가 없기 때문입니다.
- 대부분의 경우, 반복문이 재귀 함수보다 빠르게 실행됩니다.
반복문의 단점
- 코드가 재귀에 비해 복잡해지고 가독성이 떨어질 수 있습니다.
- 비선형 데이터 구조를 탐색하는 경우 반복문 사용이 어려울 수 있습니다.

그러나 재귀 함수는 동일한 문제에 대해 새로운 관점을 제시합니다. 팩토리얼 문제를 재귀적으로 바라본다면, n 팩토리얼은 단순히 (n - 1) 팩토리얼에 n을 곱함으로써 계산될 수 있습니다. 이 방법을 사용하면 (n - 1) 팩토리얼 같은 이전의 계산 과정에 대해 깊이 고민할 필요가 없어지며, 문제를 더 간결하고 관리하기 쉬운 형태로 단순화하는 데 도움이 됩니다.

public int factorial(int n) {
    if(n == 0) return 1;
    else return factorial(n - 1) * n;
}

재귀의 장점
- 재귀는 코드를 간결하고 명확하게 만들어줍니다. 복잡한 반복문을 사용하는 대신 간단하고 이해하기 쉬운 코드로 바꾸어 줍니다.
- 재귀를 사용하면 데이터 구조가 자연스럽게 처리되며, 특히 트리 같은 비선형 데이터 구조에 대해 우아하게 동작합니다.
재귀의 단점
- 재귀는 콜 스택에 함수 호출에 대한 정보를 저장하기 때문에 메모리 사용량이 크다는 단점이 있습니다.
- 또한, 재귀가 깊어질수록 스택 오버플로우의 위험이 증가합니다.

결국 어떤 방법을 선택할 것인지는 문제의 성격, 해결하려는 특정 문제에 대한 규모와 복잡성 그리고 개발자의 취향에 따라 달라집니다. 상황에 따라 가장 적합하고 효과적인 방법을 선택하는 것이 중요합니다. 💡

Algorithm