재귀함수에 대해서

재귀함수란?

재귀함수는 함수가 자기 자신을 다시 호출하는 함수를 말합니다.

• 반복문과 마찬가지로 같은 작업을 반복할 때 사용됩니다.
• 일반적으로 문제를 작은 단위로 나누어 풀 때 유용합니다.

📌 재귀함수의 필수 조건

재귀함수를 사용할 때는 반드시 두 가지를 기억해야 합니다.

1. 종료 조건(Base Case)
   재귀호출이 계속되지 않고 종료되는 조건이 필요합니다.

2. 반복 조건(Recursive Case)
   자기 자신을 다시 호출하면서 문제를 조금씩 줄여나가야 합니다.

🚩 예제 1) 팩토리얼(Factorial)

팩토리얼은 다음과 같이 정의됩니다.

n! = n × (n-1) × (n-2) × ... × 1

재귀적으로 표현하면 다음과 같습니다.

n! = n × (n-1)!

✅ 자바(Java) 예시

public class Factorial {
    public static int factorial(int n) {
        if (n <= 1) { // 종료 조건 (Base Case)
            return 1;
        } else {      // 재귀 조건 (Recursive Case)
            return n * factorial(n - 1);
        }
    }

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

출력 결과

5! = 120

✅ 파이썬(Python) 예시

def factorial(n):
    if n <= 1:        # 종료 조건 (Base Case)
        return 1
    else:             # 재귀 조건 (Recursive Case)
        return n * factorial(n - 1)

print("5! =", factorial(5))

출력 결과

5! = 120

🚩 예제 2) 피보나치(Fibonacci) 수열

피보나치 수열은 앞의 두 숫자를 더해서 다음 숫자를 만들어가는 수열입니다.

1, 1, 2, 3, 5, 8, 13, ...

재귀적 표현:

Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

✅ 자바(Java) 예시

public class Fibonacci {
    public static int fib(int n) {
        if (n <= 1) {      // 종료 조건 (Base Case)
            return n;
        } else {           // 재귀 조건 (Recursive Case)
            return fib(n - 1) + fib(n - 2);
        }
    }

    public static void main(String[] args) {
        int result = fib(6);
        System.out.println("피보나치 수열의 6번째 값: " + result);
    }
}

출력 결과

피보나치 수열의 6번째 값: 8

✅ 파이썬(Python) 예시

def fib(n):
    if n <= 1:           # 종료 조건 (Base Case)
        return n
    else:                # 재귀 조건 (Recursive Case)
        return fib(n-1) + fib(n-2)

print("피보나치 수열의 6번째 값:", fib(6))

출력 결과

피보나치 수열의 6번째 값: 8

📌 재귀함수의 장점과 단점

👍 장점

• 복잡한 문제를 간결하고 직관적으로 표현 가능
• 코드가 이해하기 쉬워짐 (문제에 따라 다름)

👎 단점

• 스택 메모리를 많이 소모 (큰 데이터에선 비효율적)
• 종료 조건을 잘못 설정하면 무한 루프가 발생할 수 있음
• 반복문보다 실행 속도가 느릴 수 있음

일반적으로 간단한 문제는 재귀를, 성능과 메모리가 중요한 경우 반복문을 권장합니다.

🚩 한 줄 정리

재귀함수는 함수가 자기 자신을 호출하는 방식으로, 종료 조건을 명확히 정의해야 하며, 복잡한 문제를 직관적이고 간결하게 표현할 때 유용합니다.