C++ 재귀 함수로 문장(문자열)을 뒤집는 방법 – 예제 코드와 동작 원리

문자열(string)은 널 문자('\0')로 끝나는 1차원 문자 배열입니다. 문자열의 역순(reversed string)이란 같은 문자열을 반대 순서로 나열한 것을 의미합니다. 예를 들어 다음과 같습니다.

원본 문자열: Apple is red
뒤집힌 문자열: der si elppA

아래는 재귀(recursion)를 사용하여 문자열 형태의 문장을 뒤집는 C++ 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;
void reverse(char *str) {
    if(*str == '\0')
        return;
    else {
        reverse(str+1);
        cout<<*str;
    }
}
int main() {
    char str[] = "C++ is fun";
    cout<<"Original String: "<<str<<endl;
    cout<<"Reversed String: ";
    reverse(str);
    return 0;
}

실행 결과

Original String: C++ is fun
Reversed String: nuf si ++C

코드 설명

위 프로그램에서 reverse() 함수는 문자열을 뒤집는 역할을 하는 재귀 함수입니다.

함수가 처음 호출되면 문자열의 시작 위치를 가리키는 포인터 *str을 매개변수로 받습니다. 현재 문자가 널 문자('\0')이면 더 이상 출력할 내용이 없으므로 함수는 즉시 반환됩니다. 널 문자가 아니라면 str+1, 즉 문자열의 다음 문자를 인자로 전달하며 자기 자신을 재귀적으로 호출합니다.

이렇게 호출이 반복되다가 문자열의 끝(널 문자)에 도달하면, 재귀 호출이 하나씩 되돌아오면서(stacking 해제) 각 문자가 뒤에서부터 앞으로 출력됩니다. 그 결과 뒤집힌 문자열이 화면에 표시됩니다. 핵심 로직은 다음 코드 조각에 담겨 있습니다.

if(*str == '\0')
    return;
else {
    reverse(str+1);
    cout<<*str;
}

main() 함수에서는 문자열을 초기화하고, 원본 문자열과 뒤집힌 문자열을 차례로 출력합니다.

char str[] = "C++ is fun";
cout<<"Original String: "<<str<<endl;
cout<<"Reversed String: ";
reverse(str);

재귀 호출의 동작 흐름

"C++ is fun"을 예로 들면, reverse() 함수는 먼저 문자열 끝까지 순차적으로 진입한 뒤, 호출이 종료되며 되돌아오는 과정에서 각 문자를 출력합니다. 출력 순서는 'n' → 'u' → 'f' → ' '(공백) → 's' → 'i' → ' ' → '+' → '+' → 'C'이며, 최종적으로 "nuf si ++C"가 완성됩니다.

시간 및 공간 복잡도

이 알고리즘은 문자열의 모든 문자를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 다만 재귀 호출마다 스택 프레임이 쌓이므로 공간 복잡도 역시 O(n)입니다. 따라서 매우 긴 문자열을 다룰 때는 스택 오버플로우를 피하기 위해 반복문 기반 구현을 고려하는 것이 좋습니다.