1부터 n까지의 합을 반환하는 알고리즘

Q. 자연수 n이 주어졌을 때 1부터 n까지의 합을 반환하는 함수 sum()을 구현하시오.

A1. 반복문을 이용하는 방법

for문 내에서 i가 1부터 5까지 1씩 증가하며 result 변수에 누적합을 저장한다.

 

class Test {
    public static void main(String[] args) {
        System.out.println("1~5 까지의 합계: " + sum(5));
    }
    
    public static int sum(int number) {
        int result = 0;
        for (int i = 1; i <= number; i++) {
            result += i;	// result = result + i와 동일
        }
        
        return result;
    }
}

 

i	+=(산술 후 할당) 연산 전 result	+=(산술 후 할당) 연산 후 result
1	0	0+1
2	1	1+2
3	3	3+3
4	6	6+4
5	10	10+5

 

 

A2. 재귀를 이용하는 방법

n + 재귀함수(n-1)을 반환하는 함수를 재귀적으로 호출한다.

n이 1이면 재귀함수를 종료하고 값을 반환한다.

 

class Test {
    public static void main(String[] args) {
        System.out.println("1~5 까지의 합계: " + sum(5));
    }
    
    public static int sum(int number) {
        if (number == 1) return 1;
        return number + sum(number - 1);
    }
}

 

sum(5) = 5 + 4 + 3 + 2 + 1

sum(4) = 4 + 3 + 2 + 1

sum(3) = 3 + 2 + 1

sum(2) = 2 + 1

sum(1) = 1