정보처리기사 정처기 | 재귀함수(Recursion Function) | 필기&실기 개념

 

⭕ 정보처리기사 정처기 | 재귀함수(Recursion Function) | 필기&실기 개념

재귀 함수(Recursive Function)는 함수가 자기 자신을 호출하는 프로그래밍 기법으로, 문제를 더 작은 부분으로 나누어 해결하는 데에 사용됩니다. 재귀 함수는 수학적인 점화식과 유사한 방식으로 문제를 해결할 때 특히 유용합니다. 이 글에서는 재귀 함수의 개념, 장단점, 그리고 주의할 점에 대해 알아보겠습니다.

 

➡️ 특징

1. 자기 호출 (Self-calling): 함수 내에서 자기 자신을 호출합니다.
2. 종료 조건 (Base case): 재귀 호출이 무한히 반복되지 않도록 하기 위해, 특정 조건이 충족되면 재귀 호출을 멈추는 종료 조건이 필요합니다.

---

예를 들어, 팩토리얼을 계산하는 재귀 함수는 다음과 같습니다.

int factorial(int n) {
    if (n <= 1) {
        return 1; // 종료 조건
    } else {
        return n * factorial(n - 1); // 자기 호출
    }
}

 

➡️ 장점

1. 가독성과 간결성: 일부 문제는 재귀적인 접근이 논리적이고 간결한 해결책을 제공할 수 있습니다.
2. 코드의 모듈화: 재귀 함수를 사용하면 큰 문제를 해결하기 위해 작은 부분 문제로 나눌 수 있으므로 코드의 모듈화가 가능합니다.

 

➡️ 단점

1. 성능: 일부 재귀 함수는 반복문에 비해 느릴 수 있습니다. 각 호출은 함수 호출 스택에 추가되어 공간을 차지하므로 스택 오버플로우가 발생할 수 있습니다.
2. 이해의 어려움: 재귀 함수를 이해하려면 문제를 작은 부분으로 어떻게 나누고 해결하는지에 대한 이해가 필요합니다. 초보자에게는 복잡해 보일 수 있습니다.

 

➡️ 주의할 점

1. 종료 조건의 중요성: 재귀 함수에서는 종료 조건을 반드시 정의해야 합니다. 그렇지 않으면 무한히 함수가 호출되어 스택 오버플로우가 발생할 수 있습니다.
2. 성능 고려: 재귀 함수는 모든 경우에 대해 효율적이지 않을 수 있습니다. 어떤 경우에는 반복문을 사용하는 것이 더 효율적일 수 있습니다.

 

⭕ [예시] 

➡️ 2023년도 3회 실기 기출 - 8. [C 언어 코드] 알맞은 출력 값을 작성하시오.

#include <stdio.h>

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

int main() {
    printf("%d", factorial(7));
    return 0;
}

정답

5040

해설

재귀 함수(Recursive Function)는 함수가 자기 자신을 호출하는 특별한 유형의 함수입니다. 여기서 주어진 코드에서 factorial 함수가 재귀 함수입니다. 재귀 함수를 이해하기 위해 코드를 세부적으로 살펴보겠습니다:

---

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

 

이 함수는 정수 n을 매개변수로 받아 팩토리얼을 계산합니다. 여기서 팩토리얼은 양의 정수 n에 대해 n! = n * (n-1) * (n-2) *... * 2 * 1의 값을 나타냅니다.

---

1. 함수는 입력 값 n을 받습니다.
2. if (n <= 1)은 종료 조건입니다. 만약 n이 1 이하이면, 1을 반환하고 재귀 호출을 종료합니다. 이는 팩토리얼의 기본 정의에서 기저 사례를 처리하는 부분입니다.
3. 그렇지 않으면, n * factorial(n - 1)을 반환합니다. 이는 현재 함수가 자기 자신을 호출하는 부분이며, 호출된 함수는 다시 n-1에 대한 팩토리얼을 계산하게 됩니다.
4. 이 과정은 n이 1이 될 때까지 반복됩니다. 재귀 호출이 깊어짐에 따라 n이 감소하고, 마지막에는 종료 조건에 도달하여 재귀 호출이 중단됩니다.

---

따라서 이 코드는 7의 팩토리얼을 계산하여 출력하게 됩니다. 재귀 함수를 사용하면 팩토리얼 계산과 같은 반복적인 작업을 간단하게 표현할 수 있습니다.

---

[정보처리기사/[최신] 실기 기출] - [2023년도 3회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리

[2023년도 3회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리

 

⭕ [예시] 

➡️ 2023년도 3회 실기 기출 - 11. [JAVA 코드] 주어진 재귀 함수와 규칙에 따라 결과를 계산하시오.

[규칙]

int recursiveFunction(int n) {
    if (n == 1) {
        return 1;
    } else {
        return recursiveFunction(n - 1) + (n - 3);
    }
}

[계산해야 하는 값]

int answer = recursiveFunction(4);
System.out.println("f(4) = " + answer);

정답

f(4) = f(3) + (4 - 3)
     = (f(2) + 1) + 1
     = ((f(1) + 1) + 1) + 1
     = 2

해설

여기서, 함수는 입력값 n에 대해 다음 규칙에 따라 동작합니다.

• 만약 n이 1이면, 함수는 1을 반환합니다.
• 그 외의 경우, 함수는 recursiveFunction(n - 1) + (n - 3)을 반환합니다.

---

이제 주어진 문제에서 계산해야 하는 값은 f(4)입니다.

1. 처음에 f(4)를 호출하면, 함수는 f(3) + (4 - 3)을 반환합니다.
2. 다음으로 f(3)을 계산하기 위해 함수는 f(2) + 1을 반환합니다.
3. 또한 f(2)를 계산하기 위해 함수는 f(1) + 1을 반환합니다.
4. 마지막으로 f(1)은 1을 반환합니다.

---

[정보처리기사/[최신] 실기 기출] - [2023년도 3회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리

[2023년도 3회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리