재귀 vs 루프: 선택 기준

1. 한 문제 — 두 가지 표현

처음 재귀를 접하면 많은 사람이 이렇게 반응합니다: «오, 이건 마법이다». 반대로 길고 많은 변수가 있는 루프를 처음 보면: «오, 이건 마법인데 악랄하다». 사실 두 형태는 같은 과정을 기록하는 다른 방식일 뿐입니다: 종료 조건에 도달할 때까지 단계를 반복합니다. 이 강의에서는 «내가 보기 좋다»가 아니라 «이해하기 쉽고 고장 내기 어렵다»는 기준으로 형태를 선택하는 법을 배웁니다.

정직한 명제부터 시작합시다: 많은 문제는 재귀와 루프 모두로 해결할 수 있습니다. 하지만 코드는 사람(그리고 컴파일러가 있지만 적어도 들여쓰기로 판단하지는 않음)이 읽습니다. 따라서 형태 선택은 가독성, 예측 가능성, 그리고 흔한 오류의 수와 관련된 문제입니다.

철학으로 빠지지 않기 위해 간단한 기준을 기억합시다: 재귀 버전에서 «한 단계에 무엇이 일어나는지»와 «어떻게 기본 사례로 수렴하는지»를 쉽게 설명할 수 있다면 재귀가 좋은 후보가 될 수 있습니다. 반대로 무한 루프에 빠지지 않을지 계속 눈으로 확인해야 한다면, 루프가 더 투명한 그림을 제공할 가능성이 있습니다.

대응 지도: 재귀 ↔ 루프

재귀를 루프로(또는 그 반대로) 변환할 때, 코드를 «처음부터 쓰지» 않고 구성 요소를 대응시키면 매우 도움이 됩니다. 이는 한 언어에서 다른 언어로 번역하는 것과 비슷합니다: «테이블»이라는 단어를 잊었을 때는 «컵이 놓이는 것»이라고 말할 수 있지만, 단어를 아는 편이 낫습니다.

아래는 유용한 대응표입니다. 암기용이 아니라 참고용으로 두세요.

초보자가 자주 하는 실수는 재귀가 «스스로 최적화된다»거나 «스스로 멈춘다»고 생각하는 것입니다. 아닙니다. 재귀는 오직 더 이상 자기 호출이 일어나지 않는 조건을 여러분이 작성했기 때문에 멈춥니다. 루프도 마찬가지로 조건을 작성하고 변수를 갱신해 조건이 거짓이 되도록 해야 멈춥니다. 마법은 없습니다. 있는 건 여러분과 길을 가는 동안 -1을 잃지 않는 능력뿐입니다.

2. 예제 1: 팩토리얼 — 두 버전, 같은 의미

팩토리얼은 재귀의 상징과 같습니다. 수식 자체가 재귀적이라 처음 보여주기 좋습니다: n! = n * (n-1)!. 하지만 여기서 중요한 것은 팩토리얼이 재귀와 루프 둘 다 자연스럽게 표현된다는 점이며, 가독성에 따라 선택할 수 있다는 것입니다.

재귀 버전

기본 사례와 단계가 어디인지 최대한 명확하게 쓰겠습니다.

#include <iostream>

long long factorial_rec(int n) {
    if (n == 0) return 1;              // 기본 사례
    return n * factorial_rec(n - 1);   // 재귀 단계
}

이 코드를 소리 내어 읽으면 논리가 명확합니다: «0이면 1을 반환하고, 그렇지 않으면 n에 factorial(n-1)을 곱해서 반환한다». 수학과 코드가 서로 충돌하지 않는 드문 경우입니다.

루프 버전

같은 논리를 스택에 «잠수»하지 않고 씁니다.

#include <iostream>

long long factorial_loop(int n) {
    long long result = 1;              // 곱셈의 항등원
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

초보자에게는 루프가 더 직관적일 수 있습니다: result가 답을 축적하고, i가 2에서 n까지 이동합니다. «반환 후에 곱한다» 같은 사고를 하지 않아도 되고, 모든 일이 같은 평면에서 진행됩니다.

3. 예제 2: 문자열을 역순으로 출력

문자열을 역순으로 출력하는 문제입니다. 뒤로 가는 인덱스 루프를 쓸 수도 있지만, 재귀는 «먼저 끝까지 가서, 그다음 출력한다»라는 매우 깔끔한 아이디어를 제공합니다.

가독성의 핵심: 호출 전과 반환 시에 실행

여기서 재귀의 장점과 함정이 드러납니다. 재귀 함수에서는 동작을 재귀 호출 전이나 후에 둘 수 있습니다. 루프에서도 가능하지만 루프에서는 보통 각 단계가 시간상 앞으로 진행되기 때문에 순서가 더 분명합니다.

문제는 «재귀 호출 후»에 실행된다는 것이 스택을 타고 돌아오면서 실행된다는 의미라는 점입니다. 즉 실행 순서가 역전됩니다.

문자열에서 이 점이 가장 잘 드러납니다.

재귀: 반환 시에 출력

#include <iostream>
#include <string>

void print_reverse_rec(const std::string& s, std::size_t i) {
    if (i == s.size()) return;     // 기본: 끝에 도달함
    print_reverse_rec(s, i + 1);   // 더 깊이 들어감
    std::cout << s[i];             // 반환 시 출력
}

다음처럼 실행하면:

int main() {
    print_reverse_rec("abcd", 0);
    std::cout << '\n';             // dcba
}

결과는 dcba입니다. 이것은 «재귀의 마법»이 아니라 단순한 순서입니다: 먼저 i가 == size가 될 때까지 가고, 그다음 반환하면서 i가 size-1, size-2... 순으로 출력합니다.

루프: 역인덱스로 출력

#include <iostream>
#include <string>

void print_reverse_loop(const std::string& s) {
    for (std::size_t i = s.size(); i > 0; --i) {
        std::cout << s[i - 1];
    }
}

호출 예:

int main() {
    print_reverse_loop("abcd");
    std::cout << '\n';             // dcba
}

루프도 훌륭하지만 경계를 조심해야 합니다: 조건은 i > 0이고 인덱스는 i - 1입니다. 그렇지 않으면 유명한 size_t 문제에 걸릴 수 있습니다: size_t는 부호 없는 타입이라 음수가 되지 못하고 큰 값으로 래핑되어 의도치 않은 동작이 발생합니다.

재귀를 루프로 번역하기: «바로 결과를 모으기»와 «나중에 모으기»

여기서 한 가지 생각을 정리해둡니다: 모든 재귀가 루프로 «직선적으로» 쉽게 바뀌는 것은 아닙니다. 팩토리얼이나 합계는 결과를 변수에 누적할 수 있기 때문에 보통 쉽게 변환됩니다.

하지만 재귀에서 주요 효과가 «반환 시» 실행되었다면, 루프로 바꿀 때 역방향으로 순회하거나 먼저 끝까지 가서 나중에 역순으로 처리해야 할 때가 많습니다.

문자열의 경우 역방향 인덱스로 충분하지만, 더 복잡한 문제(예: 깊이 우선 순회)는 더 흥미로운 대응을 요구합니다. 오늘은 실행 순서의 원칙만 다루겠습니다.

예를 들어 1부터 n까지의 합은 본질적으로 «호출 전»에 효과가 발생하지만 표현은 n + sum_to(n - 1)처럼 «이후에 더한다»로 보일 수 있습니다.

4. 예제 3: 1..n의 합 — 재귀와 루프

재귀

#include <iostream>

int sum_to_rec(int n) {
    if (n == 0) return 0;          // 기본: 합의 항등원
    return n + sum_to_rec(n - 1);
}

루프

#include <iostream>

int sum_to_loop(int n) {
    int sum = 0;                   // 재귀의 기본값과 같은 의미
    for (int i = 1; i <= n; ++i) {
        sum += i;
    }
    return sum;
}

두 경우 모두 핵심은 항등원입니다: 합은 0, 곱은 1입니다. 이것을 혼동하면 코드가 컴파일되고 동작할 수도 있지만 엉뚱한 결과를 내놓습니다. 때로는 컴파일러도 예술가가 되고 싶어하지만 보통은 실패합니다.

5. 선택 기준: 재귀를 쓸지 루프를 쓸지 결정하는 방법

«범용 규칙»을 제시하고 싶지만, 솔직히 말해 범용 규칙은 없습니다. 대신 초보자가 좋은 선택을 하도록 도와주는 실용적인 기준들이 있습니다.

첫 번째 기준 — 종료의 투명성. 루프에서는 보통 for/while 헤더에서 종료 조건을 바로 볼 수 있습니다. 재귀에서는 종료가 기본 사례에 숨겨져 있고, 그것을 놓치거나 도달하지 못하면 함수는 계속 자기 자신을 호출합니다. 따라서 재귀를 쓴다면 기본 사례가 빨리 눈에 띄도록 작성해야 합니다.

두 번째 기준 — 동작의 순서. «먼저 깊이 들어가고, 반환 시에 동작한다»고 생각하기 편하면 재귀가 읽기 좋습니다. 문자열 예제가 바로 그런 경우입니다. 반면 «각 단계에서 작은 일을 한다»는 사고가 자연스럽다면 루프가 더 읽기 쉬울 때가 많습니다. 특히 누적 변수가 있을 때 그렇습니다.

세 번째 기준 — 움직이는 요소의 수. 때로는 재귀 버전이 짧고 «수학적»으로 보이지만, 루프 버전은 인덱스, 경계, 검사들로 덩치가 커져서 관리하기 어려워집니다. 반대로 재귀가 여러 매개변수를 전달해야 하거나 «전에/후에»가 뒤섞여 이해하기 어려워질 수 있습니다. 현재 수준에서 실수할 가능성이 적은 쪽을 선택하세요.

네 번째 기준 — 이해의 지역성. 루프는 보통 위에서 아래로 읽어 한 흐름처럼 이해됩니다. 재귀는 호출을 «펼쳐서» 여러 레벨을 상상해야 하므로 그 능력이 아직 부족하면 비용이 큽니다. 초반에는 명확한 이점이 없다면 루프를 더 자주 선택하는 것이 괜찮습니다.

이걸 말로만 두지 않고 작은 표로 정리해봅니다. 성능이나 메모리 얘기는 별도 강의에서 다루겠습니다. 여기서는 오직 가독성과 오류 위험만 다룹니다.

6. 콘솔 애플리케이션의 reverse 명령

강의를 장난스러운 함수 모음으로만 끝내지 않기 위해, 간단한 콘솔 애플리케이션 컨셉을 이어갑니다. 이 앱은 명령을 받아 문자열에 대한 작은 조작을 수행합니다. 완전한 제품을 만드는 것이 목적은 아니고, 작은 함수를 작성해 main에 연결하는 연습이 목적입니다.

사용자가 명령과 문자열을 입력하면 결과를 출력하는 모드가 있다고 가정합시다. reverse라는 명령을 추가하고, 학습용으로 구현을 전환할 수 있게 합니다.

다음은 명령 처리기의 골격입니다:

#include <iostream>
#include <string>

void run_reverse_command() {
    std::string s;
    std::getline(std::cin, s);

    // 현재는 그냥 출력만 함, 나중에 확장 가능.
    // 구현은 아래에서 선택함.
}

이제 두 가지 출력 함수를 추가합니다(이미 봤지만 함께 모아두어 연결하기 편하게).

#include <iostream>
#include <string>

void print_reverse_rec(const std::string& s, std::size_t i) {
    if (i == s.size()) return;
    print_reverse_rec(s, i + 1);
    std::cout << s[i];
}

그리고 루프 버전:

#include <iostream>
#include <string>

void print_reverse_loop(const std::string& s) {
    for (std::size_t i = s.size(); i > 0; --i) {
        std::cout << s[i - 1];
    }
}

이제 명령 내부에서 구현을 «전환»해 가독성을 비교할 수 있습니다:

#include <iostream>
#include <string>

void run_reverse_command() {
    std::string s;
    std::getline(std::cin, s);

    const bool use_recursion = true; // 학습용 플래그

    if (use_recursion) {
        print_reverse_rec(s, 0);
    } else {
        print_reverse_loop(s);
    }

    std::cout << '\n';
}

전체 로직을 한 함수에 섞지 않는 점을 주목하세요. 실제 코드에서는 이게 정신 건강을 지킵니다: main은 «지휘자»로 남고, 스스로 모든 악기를 연주하는 오케스트라가 되지 않습니다.

미니 순서도: 재귀적 역출력 시 일어나는 일

때로는 순서를 문자 그대로 보는 것이 유용합니다: 먼저 들어가고, 그다음 반환합니다. 해결에 필수는 아니지만 머리속 디버거에 매우 도움이 됩니다.

flowchart TD
    A["print_reverse_rec(i=0)"] --> B["print_reverse_rec(i=1)"]
    B --> C["print_reverse_rec(i=2)"]
    C --> D["print_reverse_rec(i=3)"]
    D --> E["i==size -> return"]
    E --> D2["s[2] 출력"]
    D2 --> C2["s[1] 출력"]
    C2 --> B2["s[0] 출력"]

이 그림은 우리가 논의한 바를 정확히 보여줍니다: 동작이 재귀 호출 이후에 있으므로 반환 시에 실행됩니다.

7. 흔한 실수

실수 #1: 기본 사례에 해당하는 것을 혼동해 누적 변수의 초기값을 잘못 설정함.
재귀에서는 기본 사례에서 올바른 값을 반환합니다(0은 합, 1은 곱). 루프에서는 이것이 누적 변수의 초기값이 됩니다. 습관적으로 모든 곳에 0을 넣으면 팩토리얼은 항상 0이 되어 «수학을 빠르게 파괴하는» 완벽한 모델이 됩니다.

실수 #2: 재귀를 루프로 옮길 때 동작 순서를 잃음.
재귀에서 동작이 반환 시에 실행되었다면(재귀 호출 후), 직진 루프로 바꿀 경우 순서가 달라질 수 있습니다. 문자열 예제에서 이는 특히 두드러져서 dcba 대신 abcd가 될 수 있습니다. 이런 경우 역방향 순회를 하거나, 읽기 측면에서 재귀를 유지하는 편이 낫습니다.

실수 #3: 변환 후 루프 경계(off-by-one)를 틀리게 작성함.
재귀의 조건 if (i == s.size()) return는 «끝에 도달하면 멈춤»을 정확히 표현합니다. 이를 루프로 옮길 때 i <= s.size()처럼 쓰면 우연히 s[s.size()]에 접근해 경계를 벗어날 수 있습니다. 치료법은 단순하고 지루하지만 효과적입니다: 기본 사례와 루프 경계를 꼼꼼히 대조하고 특히 <와 <=를 조심하세요.

실수 #4: std::size_t로 뒤로 가는 루프를 만들어 «음수 아래로 가는» 문제를 일으킴.
다음 패턴은 직관적으로 보일지 모릅니다: for (std::size_t i = s.size() - 1; i >= 0; --i). 하지만 size_t는 음수가 될 수 없으므로 i >= 0 조건은 사실상 항상 참입니다. 결과적으로 루프는 무한(또는 거의 무한)해지고 엉뚱한 출력이 나옵니다. 안전한 형태는 for (std::size_t i = s.size(); i > 0; --i)이고, 출력은 s[i - 1]처럼 해야 합니다.

실수 #5: 코드 길이로 «재귀냐 루프냐»를 결정함.
가끔 재귀가 3줄이라 예쁘게 보이지만, 일주일 뒤에 자신도 어디가 기본이고 왜 안 터지는지 이해하지 못할 수 있습니다. 반대로 루프가 7줄이라 길어 보여도 유지보수 측면에서는 더 명확할 수 있습니다. 목표는 줄 수에서 이기는 것이 아니라, 뜨개질하듯 코드를 해석하지 않아도 유지관리할 수 있는 코드를 작성하는 것입니다.