C++ 재귀 함수로 자연수의 합 구하기: 완벽 가이드

자연수(natural number)란 1부터 시작하는 양의 정수를 의미합니다. 자연수의 나열은 다음과 같습니다.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10……

이 글에서는 재귀(recursion) 기법을 사용하여 첫 n개의 자연수 합을 구하는 C++ 프로그램을 소개합니다. 반복문(for, while) 없이도 함수가 스스로를 호출하는 방식으로 간결하게 문제를 해결할 수 있습니다.

전체 예제 코드

#include <iostream>
using namespace std;

int sum(int n) {
    if(n == 0)
        return n;
    else
        return n + sum(n-1);
}

int main() {
    int n = 10;
    cout << "Sum of first " << n << " natural numbers is " << sum(n);
    return 0;
}

실행 결과

Sum of first 10 natural numbers is 55

코드 동작 원리

위 프로그램에서 핵심 역할을 하는 것은 sum()이라는 재귀 함수입니다. 이 함수의 동작 방식은 다음과 같습니다.

• 기저 조건(Base Case): n이 0이면 0을 반환합니다. 첫 0개의 자연수의 합은 당연히 0이기 때문입니다.
• 재귀 호출(Recursive Case): n이 0보다 크면 자신을 sum(n-1) 형태로 다시 호출하고, 그 결과에 n을 더하여 반환합니다.

이 과정을 통해 함수는 n, n-1, n-2, …, 2, 1을 차례대로 더하게 되며, 최종적으로 첫 n개 자연수의 전체 합이 계산됩니다. 해당 로직을 담당하는 코드는 아래와 같습니다.

int sum(int n) {
    if(n == 0)
        return n;
    else
        return n + sum(n-1);
}

결과 출력하기

main() 함수에서는 cout을 사용하여 계산된 결과를 화면에 출력합니다. 출력 부분의 코드는 다음과 같습니다.

cout<<"Sum of first "<<n<<" natural numbers is "<<sum(n);

정리

재귀를 활용하면 자연수의 합처럼 반복적인 구조를 가진 문제를 매우 직관적인 코드로 표현할 수 있습니다. 다만 n이 매우 클 경우 스택 오버플로(stack overflow)가 발생할 수 있으므로, 실무에서는 입력 크기를 고려하거나 반복문·수학 공식(n*(n+1)/2)을 대안으로 활용하는 것이 좋습니다.