C++ 재귀 함수로 수열 1^1 + 2^2 + 3^3 + … + n^n의 합 구하기

이 문제에서는 숫자 n이 주어지며, 이 값은 수열 1^1 + 2^2 + 3^3 + … + n^n의 마지막 항을 결정합니다. 목표는 이 수열의 전체 합을 구하는 프로그램을 작성하는 것이며, 여기서는 반복문 대신 재귀(recursion)를 활용해 문제를 해결해 보겠습니다.

예제로 문제 이해하기

입력

n = 4

출력

288

설명 − sum = (1^1) + (2^2) + (3^3) + (4^4) = 1 + 4 + 27 + 256 = 288.

재귀를 활용한 접근 방법

재귀 방식에서는 두 개의 함수를 사용합니다.

• 거듭제곱 함수(power) : base의 exp 제곱을 재귀적으로 계산합니다. exp가 0이면 1을 반환하고, 그렇지 않으면 base × power(base, exp−1)을 반환합니다.
• 수열 합 함수(calcSeriesSum) : n이 0이면 0을 반환해 재귀를 종료하고, 그렇지 않으면 n^n을 더한 뒤 n−1에 대해 자기 자신을 다시 호출합니다.

알고리즘

함수 power(base, exp):
    exp == 0 이면 1 반환
    아니면 base * power(base, exp - 1) 반환

함수 calcSeriesSum(n):
    n == 0 이면 0 반환
    아니면 power(n, n) + calcSeriesSum(n - 1) 반환

main:
    n을 입력받음
    calcSeriesSum(n)의 결과 출력

예제 코드

다음 프로그램은 위 알고리즘이 실제로 동작하는 과정을 보여줍니다.

#include <iostream>
using namespace std;

// base의 exp 제곱을 재귀적으로 계산하는 함수
long long power(int base, int exp) {
    if (exp == 0)
        return 1;
    return base * power(base, exp - 1);
}

// 수열 1^1 + 2^2 + ... + n^n의 합을 재귀적으로 계산하는 함수
long long calcSeriesSum(int n) {
    if (n == 0)          // 재귀 종료 조건
        return 0;
    return power(n, n) + calcSeriesSum(n - 1);
}

int main() {
    int n = 7;
    cout << "수열 1^1 + 2^2 + 3^3 + ... + " << n << "^" << n << " 의 합 : " << calcSeriesSum(n);
    return 0;
}

실행 결과

수열 1^1 + 2^2 + 3^3 + ... + 7^7 의 합 : 873612

참고 사항

n이 커지면 n^n 값이 매우 빠르게 증가하므로, 오버플로를 방지하려면 합과 거듭제곱 값을 저장할 때 long long 타입을 사용하는 것이 좋습니다. 또한 각 항을 단순 재귀로 계산할 경우 전체 연산 횟수는 O(n²) 수준이 되는데, 필요하다면 분할 정복 기반의 빠른 거듭제곱(O(log n)) 기법으로 최적화할 수 있습니다.