백준 알고리즘 8393번: 합 [C++][재귀]

문제 출처: www.acmicpc.net/problem/8393

8393번: 합

 

1. 코드

	#include <iostream>
	using namespace std;
	int sum(int n)
	{
	if (n == 1)
	return 1;
	else
	return n + sum(n - 1);
	}
	int main(void)
	{
	int N;
	cin >> N;
	cout << sum(N);
	return 0;
	}

view raw 8393.cpp hosted with ❤ by GitHub

(실행)

 

2. 풀이

int N;
cin >> N;

먼저 N을 입력을 한다.

cout << sum(N);

그리고 sum(N)을 출력을 할 것인데 sum() 함수에 대한 코드를 보자

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

sum() 함수는 임시적으로 만든 함수이다. 구성은 위 코드와 같다.

if (n == 1)
    return 1;
else
    return n + sum(n - 1);

n이 1이라면 1을 반환을 하는데 만약 아니라면 n + sum(n - 1)을 반환하는데 이러한 구성이 재귀이다. 실행 중인 함수에서 자기 자신을 다시 호출하는 것을 재귀라고 하는데 예시로 3을 입력을 했으면 아래 표와 같은 동작을 한다.

실행순서	return n + sum(n - 1)
1	return 3 + sum(2)
2	return 2 + sum(1)
3	return 1
4	return 2 + sum(1) ⇒ return 2 + 1 ⇒ return 3
5	return 3 + sum(2) ⇒ return 3 + 3 ⇒ return 6

그래서 결과적으로 3을 입력했을 때 3 + 2 + 1 = 6을 수행하여 6을 반환하고 그것을 출력한다.