기초 다지기: 재귀에 대한 포괄적인 가이드 (스스로를 호출하는 함수)

Source: Dev.to

재귀란 무엇인가?

자신을 계속해서 호출하여 기본 조건에 도달할 때까지 반복하는 함수를 재귀 함수라고 합니다.
이 방법은 해결하고자 하는 문제의 더 작은 단위에 자신을 복사하여 호출함으로써 문제를 해결합니다.
자신에 대한 각 호출을 재귀 단계라고 하지만, 재귀 함수는 유효한 기본 사례가 주어졌을 때 종료되는 것이 중요합니다.

문제 해결에서 재귀를 사용하는 이유는?

재귀 코드는 일반적으로 반복 코드보다 짧고 작성하기 쉬우며, 유사한 하위 작업으로 나눌 수 있는 작업에 가장 유용합니다. 흔히 사용되는 예시로는 다음과 같습니다:

• 정렬
• 검색
• 트리 순회 등.

Source:

재귀 함수의 형식

재귀 함수는 작업을 수행하는 과정에서 자신을 호출하여 하위 작업을 수행합니다. 어느 시점에서 함수는 자신을 호출하지 않고도 수행할 수 있는 하위 작업을 만나게 됩니다. 따라서 재귀 함수는 두 부분으로 나눌 수 있습니다:

A. 기본 사례 (Base Case)

기본 사례는 함수가 재귀 호출을 하지 않는 상황을 말합니다. 해결하려는 문제에 따라 재귀 함수는 하나 이상의 기본 사례를 가질 수 있습니다.

B. 재귀 사례 (Recursive Case)

재귀 사례는 함수가 자신을 호출하여 하위 작업을 수행하는 경우입니다. 재귀 함수는 하나 이상의 재귀 사례를 가질 수 있습니다.

일반 템플릿

// 기본 사례(s)
if (test for base case 1) {
    return some base case value;
} else if (test for another base case) {
    return some other base case value;
}
// …
 
// 재귀 사례(s)
else {
    // 작업을 수행하고, 재귀 호출을 함
    return some work and then a recursive call;
}

재귀 함수가 작동하는 방식

우리는 고전적인 팩토리얼 함수 n!을 예시로 들어 설명합니다.

팩토리얼 정의

• 0! = 1
• 1! = 1
• 2! = 2 × 1
• 3! = 3 × 2 × 1
• 4! = 4 × 3 × 2 × 1

패턴을 살펴보면:

• 1! = 1 × (1‑1)! → (1‑1)! = 0!
• 2! = 2 × (2‑1)! → (2‑1)! = 1!
• 3! = 3 × (3‑1)! → (3‑1)! = 2!
• 4! = 4 × (4‑1)! → (4‑1)! = 3!

따라서 재귀 관계식은 다음과 같습니다:

n! = n × (n‑1)!   if n > 0
0! = 1            (base case)

코드 예시 (Python)

def factorial(n):
    # base case
    if n == 0:
        return 1
    # recursive case
    return n * factorial(n - 1)

factorial(4)가 호출되면 다음과 같은 호출 스택이 생성됩니다 (LIFO 순서):

factorial(4)
 └─ factorial(3)
     └─ factorial(2)
         └─ factorial(1)
             └─ factorial(0)  ← base case, returns 1

각 호출은 다음 호출의 결과를 기다렸다가 스택이 풀리면서 n과 곱해 최종적으로 24를 반환합니다.

재귀와 메모리

각 재귀 호출은 호출 스택에 메서드의 변수 복사본을 새로 생성합니다. 호출이 끝나면(즉, 값을 반환하면) 해당 스택 프레임이 제거됩니다.
재귀가 기본 사례에 도달하지 못하고(무한 재귀) 계속될 경우, 스택이 계속 증가하여 프로그램이 메모리를 다 사용하게 되고 스택 오버플로우 오류가 발생합니다. 따라서 올바른 기본 사례가 필수적인 이유가 바로 이것입니다.

재귀 vs 반복

재귀 vs. 반복

재귀에 대해 논의할 때 가장 먼저 떠오르는 기본 질문은: 반복과 재귀 중 어느 쪽이 더 나은가?
답은 당신이 하려는 일에 따라 달라집니다.

• 재귀적 접근 방식은 명확한 반복 해결책이 없는 문제를 해결하기 더 간단하게 만들 때가 많습니다.
• 그러나 재귀는 각 호출마다 호출 스택에 공간이 필요하므로 오버헤드가 발생합니다.

재귀

• 기본 사례에 도달하면 종료됩니다.
• 각 재귀 호출은 스택 메모리의 추가 공간을 필요로 합니다.
• 재귀가 무한히 계속되면 프로그램이 메모리를 다 써버려 스택 오버플로가 발생할 수 있습니다.
• 일부 문제에 대한 해결책을 재귀적으로 표현하는 것이 더 쉽습니다.

반복

• 루프 조건이 false로 평가될 때 종료됩니다.
• 각 반복은 추가 스택 공간을 필요로 하지 않습니다.
• 무한 루프는 영원히 실행될 수 있지만, 반복마다 추가 메모리를 소비하지는 않습니다.
• 반복적 해결책이 항상 재귀적 해결책만큼 명확하지는 않을 수 있습니다.

재귀를 사용하는 알고리즘 예시

1. 피보나치와 팩토리얼 계산
2. 병합 정렬, 퀵 정렬
3. 이진 탐색
4. 트리 순회
5. 그래프 순회 등

친애하는 독자님, 주제에 대한 의견이나 개선 아이디어가 있으면 언제든지 댓글을 남기거나 이메일을 보내 주세요—함께 배우고 성장해요.

이 글이 도움이 되었다면 원하는 만큼 ‘클랩’을 눌러 주시고, 더 많은 글을 원하시면 팔로우도 자유롭게 해 주세요. 서로 격려하며 나아갑시다!

나와 연결하기

• X (Twitter)
• LinkedIn
• Medium