재귀 입문

Coddy C++ 여정의 로직과 흐름 섹션에 포함된 레슨 — 56개 중 45번째.

재귀(Recursion)는 함수가 문제를 해결하기 위해 자기 자신을 호출하는 프로그래밍 기법입니다. 루프를 사용하는 대신, 재귀 함수는 복잡한 문제를 직접 해결할 수 있는 간단한 사례에 도달할 때까지 더 작고 유사한 하위 문제로 나눕니다.

모든 재귀 함수는 두 가지 필수 구성 요소를 가져야 합니다. 기본 케이스(base case)는 재귀를 중단하는 조건입니다. 이것이 없다면 함수는 자기 자신을 영원히 호출할 것입니다. 재귀 단계(recursive step)는 함수가 수정된 매개변수를 사용하여 자기 자신을 호출하는 부분이며, 호출할 때마다 기본 케이스에 더 가까워집니다.

재귀를 보여주는 간단한 카운트다운 예제입니다:

void countdown(int n) {
    if (n <= 0) {           // 기저 사례: n이 0에 도달하면 중단
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // 재귀 단계: n-1로 호출
}

countdown(3)을 호출하면 3을 출력하고, countdown(2)를 호출하여 2를 출력한 뒤, 다시 countdown(1)을 호출하는 식으로 기본 케이스(base case)에 도달할 때까지 계속됩니다. 각 함수 호출은 종료되기 전에 다음 호출이 완료되기를 기다리며, 결과적으로 원래 호출자에게로 다시 되돌아가는 호출 체인을 형성합니다.

치트 시트

재귀는 문제를 더 작은 하위 문제로 나누어 해결하기 위해 함수가 자기 자신을 호출하는 것을 말합니다.

모든 재귀 함수에는 다음이 필요합니다:

기본 케이스(Base case): 재귀를 중단하는 조건
재귀 단계(Recursive step): 수정된 매개변수로 함수가 자기 자신을 호출함

카운트다운 함수 예시:

void countdown(int n) {
    if (n <= 0) {           // 기본 케이스
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // 재귀 단계
}

직접 해보기

이 레슨에는 코드 챌린지가 없습니다.