재귀 [ Recursion ] 개념 및 예제

재귀(Recursion)는 함수가 자기 자신을 호출하는 프로그래밍 기법을 의미합니다. 이 기법은 문제를 더 작은 하위 문제로 나누어 풀어나갈 때 유용하게 사용할 수 있습니다. 재귀는 코드의 간결함을 제공하지만, 올바르게 사용하지 않으면 스택 오버플로우와 같은 문제가 발생할 수 있습니다. 오늘은 재귀의 개념과 몇 가지 예제를 Java와 C 언어로 설명해 보겠습니다.

재귀의 개념

재귀 함수는 자기 자신을 호출하여 문제를 해결하는 방법입니다. 보통 재귀를 사용할 때는 두 가지 주요 구성 요소가 있습니다:

1. 기본 사례(Base Case): 함수가 더 이상 자신을 호출하지 않고 멈추게 하는 조건입니다. 이 조건이 없으면 함수는 무한 루프에 빠져 결국 스택 오버플로우가 발생합니다.
2. 재귀 사례(Recursive Case): 문제를 더 작은 문제로 나누고, 해당 문제를 해결하기 위해 자기 자신을 호출하는 부분입니다.

재귀의 예: 팩토리얼 함수

팩토리얼은 양의 정수 n에 대해 n! = n * (n - 1) * (n - 2) * ... * 1로 정의됩니다. 팩토리얼을 재귀적으로 정의하면 다음과 같습니다:

• n! = n * (n - 1)! (단, n > 1일 때)
• 0! = 1 (기본 사례)

Java로 구현한 팩토리얼 함수

public class Factorial {
    public static void main(String[] args) {
        int number = 5;
        int result = factorial(number);
        System.out.println(number + "! = " + result);
    }

    public static int factorial(int n) {
        if (n == 0) {
            return 1; // 기본 사례
        } else {
            return n * factorial(n - 1); // 재귀 사례
        }
    }
}

위 코드에서 factorial() 함수는 n이 0일 때 1을 반환하여 재귀 호출을 멈춥니다. 그 외의 경우에는 자기 자신을 호출하여 팩토리얼 값을 계산합니다.

C로 구현한 팩토리얼 함수

#include <stdio.h>

int factorial(int n) {
    if (n == 0) {
        return 1; // 기본 사례
    } else {
        return n * factorial(n - 1); // 재귀 사례
    }
}

int main() {
    int number = 5;
    int result = factorial(number);
    printf("%d! = %d\n", number, result);
    return 0;
}

C 언어에서도 유사하게 factorial() 함수가 자기 자신을 호출하여 팩토리얼을 계산합니다. 기본 사례가 n == 0일 때 함수는 1을 반환하며 종료됩니다.

재귀의 또 다른 예: 피보나치 수열

피보나치 수열은 각 숫자가 이전 두 숫자의 합으로 이루어진 수열입니다. 수열은 다음과 같이 정의됩니다:

• F(0) = 0, F(1) = 1 (기본 사례)
• F(n) = F(n-1) + F(n-2) (재귀 사례)

Java로 구현한 피보나치 함수

public class Fibonacci {
    public static void main(String[] args) {
        int n = 10;
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }

    public static int fibonacci(int n) {
        if (n == 0) {
            return 0; // 기본 사례
        } else if (n == 1) {
            return 1; // 기본 사례
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 사례
        }
    }
}

위 코드에서 fibonacci() 함수는 n이 0 또는 1일 때 값을 반환하고, 그 외의 경우에는 두 이전 값의 합을 반환하여 피보나치 수를 계산합니다.

C로 구현한 피보나치 함수

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0) {
        return 0; // 기본 사례
    } else if (n == 1) {
        return 1; // 기본 사례
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 사례
    }
}

int main() {
    int n = 10;
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    return 0;
}

C 언어로도 Java와 비슷하게 피보나치 수열을 계산하는 재귀 함수를 작성할 수 있습니다. fibonacci() 함수는 기본 사례에서 0 또는 1을 반환하고, 그 외에는 두 이전 값을 더한 결과를 반환합니다.

재귀 사용 시 주의사항

재귀 함수는 코드의 간결함과 문제를 분할하여 해결할 수 있는 강력한 도구입니다. 하지만 몇 가지 주의할 점이 있습니다:

1. 기본 사례를 명확하게 정의해야 합니다: 기본 사례가 없다면 함수는 무한히 자신을 호출하게 되고, 결국 스택 오버플로우가 발생하게 됩니다.
2. 함수 호출의 오버헤드: 재귀 호출은 반복문에 비해 호출 스택을 많이 사용하므로, 성능이 중요한 경우에는 반복문으로 대체하는 것이 좋습니다.
3. 메모이제이션 사용: 피보나치 수열과 같은 경우, 같은 값을 여러 번 계산하게 되어 비효율적일 수 있습니다. 이를 해결하기 위해 메모이제이션(Memoization) 기법을 사용하여 이전에 계산한 값을 저장하고 재사용할 수 있습니다.

Java로 메모이제이션 적용한 피보나치 함수

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemoization {
    private static Map<Integer, Integer> memo = new HashMap<>();

    public static void main(String[] args) {
        int n = 10;
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }

    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        } else {
            int result = fibonacci(n - 1) + fibonacci(n - 2);
            memo.put(n, result);
            return result;
        }
    }
}

이 코드에서는 HashMap을 사용하여 이미 계산된 피보나치 수를 저장하고, 같은 값을 다시 계산하지 않도록 합니다. 이렇게 하면 시간 복잡도를 획기적으로 줄일 수 있습니다.

C로 메모이제이션 적용한 피보나치 함수

#include <stdio.h>

#define MAX 100

// 피보나치 수열을 저장할 배열
long long memo[MAX];

// 메모이제이션이 적용된 피보나치 함수
long long fibonacci(int n) {
    if (n <= 1) {
        return n; // 기본 조건: F(0) = 0, F(1) = 1
    }

    // 이미 계산된 값이 있으면 반환
    if (memo[n] != -1) {
        return memo[n];
    }

    // 값을 계산하고 배열에 저장
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    int n;

    // 메모 배열 초기화 (-1로 설정하여 아직 계산되지 않은 것을 표시)
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;
    }

    // 사용자로부터 피보나치 수열의 위치를 입력 받음
    printf("피보나치 수열에서 원하는 위치를 입력하세요 (0 ~ %d): ", MAX - 1);
    scanf("%d", &n);

    if (n < 0 || n >= MAX) {
        printf("입력한 값이 범위를 벗어났습니다.\n");
        return 1;
    }

    // 피보나치 수열 값 출력
    printf("Fibonacci(%d) = %lld\n", n, fibonacci(n));

    return 0;
}

이 코드는 메모이제이션을 사용하여 재귀적 피보나치 함수의 중복 계산을 피하기 때문에 큰 값의 피보나치 수를 빠르게 계산할 수 있습니다.

결론

재귀 함수는 복잡한 문제를 간결하게 표현할 수 있는 강력한 도구입니다. 팩토리얼, 피보나치 수열과 같은 문제에서 재귀를 사용하여 코드를 작성하면 문제를 해결하는 과정이 직관적으로 보입니다. 하지만 재귀 호출의 오버헤드와 스택 사용량에 주의해야 하며, 경우에 따라 반복문이나 메모이제이션을 통해 성능을 개선하는 것이 필요합니다.

Java와 C 언어로 각각의 예제를 통해 재귀의 기본적인 사용 방법을 살펴보았습니다. 여러분도 재귀를 활용하여 다양한 문제를 해결해 보세요!