[재귀 알고리즘] Linear Sum (순차합)

[재귀 알고리즘] Linear Sum (순차합)

Linear Sum (순차합)

순차합은 간단히 반복문으로 구현 가능하다.

하지만 재귀적으로 생각하는 것에 많은 도움을 줄 수 있는 예제이다.

n개의 정수 $x_1, x_2, ... , x_n$가 있을 때, 주어진 정수의 합 $S(n) = \displaystyle\sum_{i=1}^{n} a_i$를 계산하는 문제이다.

$$ S(n) = \begin{cases} a_1 & \quad \text{n=1} \quad \text{(base case)}\\ S(n-1)+a_n & \quad \text{n>1} \quad \text{(recursive step)}\\ \end{cases} $$

코드를 먼저 보면,

#include <iostream>
using namespace std;
 
int linearSum(int a[], int n)
{
    if (n==1)    // base case
        return a[0];
    else         // recursive step
        return linearSum(a, n-1) + a[n-1];
}
 
int main()
{
    int a[5] = {1, 2, 3, 4, 5};
    cout << linearSum(a, 5) << endl;
    return 0;
}

순차 합을 구하는 linearSum 함수가 n이 1이 될 때까지 n을 1씩 줄여가며 자신을 호출하고 있다.

n이 1이 되면, linearSum(a, 1) 함수가 종료되며 a[0]을 linearSum(a, 2) 함수로 리턴한다.

linearSum(a, 2)는 a[0]+a[1]을 linearSum(a, 3)으로 리턴하며 종료된다.

이 과정을 linearSum(a, 5) 함수의 리턴까지 반복한다.

최종 결과는 15(1+2+3+4+5)가 출력된다.