C의 재귀

재귀는 문제를 해결하기 위해 함수가 자기 자신을 호출하는 기법입니다.

이 단원에서는 다음 내용을 학습합니다.

• 재귀의 의미와 작동 방식
• 재귀 함수를 구현하는 방법
• 재귀와 반복의 차이

재귀란 무엇인가요?

재귀는 문제의 더 작은 부분을 해결하기 위해 함수가 자기 자신을 호출하는 것입니다.

예시 구문:

void function() { function(); // Recursive call }

모든 재귀 함수에는 무한 재귀를 방지하기 위한 기저 조건이 있어야 합니다.

예시: 재귀

이 프로그램은 5부터 1까지의 숫자를 출력하며 재귀를 보여 줍니다.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

재귀의 기저 조건

재귀 함수에는 재귀를 멈추기 위한 기저 조건이 포함되어야 합니다.

예시:

if (n == 0) return;

기저 조건이 없으면 함수가 자기 자신을 무한히 호출하여 스택 오버플로가 발생합니다.

예시: 재귀를 사용한 팩토리얼

이 프로그램은 재귀를 사용하여 숫자의 팩토리얼을 계산합니다.

#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1);
}

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

재귀와 반복의 비교

재귀와 반복(반복문)은 같은 결과를 얻을 수 있지만 작동 방식은 서로 다릅니다.

차이점:

• 재귀는 함수 호출을 사용하므로 더 많은 메모리가 필요합니다.
• 반복은 반복문을 사용하므로 일반적으로 더 효율적입니다.
• 재귀는 트리 순회와 같은 문제의 코드를 더 단순하게 만들어 줍니다.

예제: 피보나치 수열(재귀)

이 프로그램은 재귀를 사용하여 피보나치 수열을 계산합니다.

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

재귀는 언제 사용하나요?

재귀는 다음과 관련된 문제에 유용합니다.

• 트리 순회
• 백트래킹(예: 미로 풀기)
• 팩토리얼과 피보나치 같은 수학 문제

요약

이 레슨에서는 다음 내용을 배웠습니다.

• 재귀가 무엇이며 어떻게 작동하는지
• 기본 사례의 중요성
• 재귀와 반복의 차이

다음으로 C에서 배열과 문자열을 살펴보겠습니다!